Graph Algorithms

In this blog we will discuss about elementary path finding algorithms .

In the next blog related to path finding we will discuss about A* algorithm.

Dijkstra Algorithm — — — — — — — — — — — — — — — — — — — — -

This is a single source shortest path algorithm .

Python implementation — -

We will make a list that keeps track of visited vertex.

We will have a list with initial distance infinite for all the entries.

The distance of the source is 0 , so that one is chosen first.

C# implementation

Bellman Ford Algorithm — — — — — — — — — — — — — — — — — — — — —

In case of Djikstra’s algorithm the negative weight of an edge may cause problem so in that case Bellman Ford’s algorithm can be used.

Python implementation (Make sure to indent the code )

Floyd-Warshall Algorithm — — — — — — — — — — — — — — — — — — — -

All pair shortest path algorithm.

We express a graph in terms of adjacency matrix and dynamically by taking certain decision get final result in terms of resultant matrix.

C# implementation

Prim’s Algorithm — — — — — — — — — — — — — — — — — — — — — — — —

To find minimum spanning tree we can use Prim’s algorithm.

  • Spanning tree — — Subset of a graph with V vertex and |V-1| edges.

To keep track of the visited vertex we will have a list / array.

The entries of distance vector will be infinite.

The source distance is 0 so that it becomes the first element to be selected.

Parent list will keep track of the initial vertex of an edge that will produce minimum spanning tree.

Python implementation — — — — — — — — — — — — — — — — — — —

C# implementation

Note : Python codes may cause indentation error because of improper indentation of medium . You can always refer to C# ones.

Take care , Bye.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store