by Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph. This algorithm can be used to find out the fastest way to reach from one place to another or it can be used to find cheapest way to fly or travel between source and destination.
A weighted graph is a graph in which every edge is not of same weight. In this weighted graph, we have to find the shortest path to all the vertices from a given vertices.
Before going ahead have a look into Graph Basics.
Let’s look into a weighted graph in which we have to calculate the shortest path to all the vertices from a given node.
Algorithm
- Define a distance array of size equal to graph node.
- If edge available from given node to any node then distance should be set to edge weight.
- initialize it to very high value (eg: 9999).
- Define a path array of size equal to graph node and initialize it to srcNode.
- Define a visited array of size equal to graph node and initialize it to false.
- Iterate through each node in Graph.
- continue if node is the given node to calculate the shortest distance.
- Iterate through distance array to find the node with minimum weight which is not yet visitied.
- Mark the node as visited.
- Find the minimum weighted node (K) which is not yet visited.
- Iterate through all nodes in graph.
- If node is not visited and edge present between K to this node and existing distance of node is larger than distance of (K) + edge [k][node] then
- Update distance[node] = distance[K] + edge[K][node]
- If node is not visited and edge present between K to this node and existing distance of node is larger than distance of (K) + edge [k][node] then
- Print the distance and path array.
After applying the above algorithm, below is the shortest path tree for above graph.
Implementation
Let’s look into a sample Graph class which we are going to use it here. Check Graph and it’s basic implementation for more details.
class Graph
{
private:
int m_nodes;
int m_edges;
int **edges;
bool isUndirected;
int isConnected;
public:
Graph (int nodes, bool isUndirected);
int getNumberOfNodes ();
int getNumberOfEdges ();
void getEdges ();
bool addEdge (int srcNode, int dstNode);
~Graph ();
void shortestPathInWeightedGraph_dijkstra (int srcNode);
};
Let’s look into the function to find shortest path using Dijkstra algorithm.
/* Dijkstra's algorithm */
void Graph::shortestPathInWeightedGraph_dijkstra (int srcNode)
{
int distance[m_nodes];
int path[m_nodes];
bool visited[m_nodes];
for (int i = 0; i < m_nodes; i++) {
if (edges[srcNode][i])
distance[i] = edges[srcNode][i];
else
distance[i] = 9999;
path[i] = srcNode;
visited[i] = false;
}
distance[srcNode] = 0;
path[srcNode] = srcNode;
visited[srcNode] = true;
for (int i = 0; i < m_nodes; i++) {
if (i == srcNode)
continue;
int min_wt = 9999, min_node = 0;
/* Pickup the node having minimum weight */
for (int j = 0; j < m_nodes; j++) {
if (!visited[j]) {
if (distance[j] < min_wt) {
min_wt = distance[j];
min_node = j;
}
}
}
visited[min_node] = true;
for (int k = 0; k < m_nodes; k++) {
if (!visited[k] && edges[min_node][k]) {
if (distance[k] > distance[min_node] + edges[min_node][k]) {
distance[k] = distance[min_node] + edges[min_node][k];
path[k] = min_node;
}
}
}
}
for (int i = 0; i < m_nodes; i++) {
cout <<"Node: " << i << " distance: " << distance[i] << " from Node: " << path[i] << endl;
}
}
Let’s define a sample graph and check how this code works.
void add_header (const char *line)
{
cout << "========================================================================" << endl;
cout << line << endl;
cout << "========================================================================" << endl;
}
int main ()
{
Graph g(7, false);
g.addEdgeWithWeight (0, 1, 3);
g.addEdgeWithWeight (0, 2, 2);
g.addEdgeWithWeight (0, 3, 6);
g.addEdgeWithWeight (2, 1, 2);
g.addEdgeWithWeight (1, 4, 6);
g.addEdgeWithWeight (1, 5, 1);
g.addEdgeWithWeight (4, 6, 1);
g.addEdgeWithWeight (5, 6, 5);
g.addEdgeWithWeight (3, 6, 2);
g.addEdgeWithWeight (5, 3, 1);
g.getEdgesIn2DFormat ();
add_header ("Finding shortest path in weighted graph from Node 0 using Dijkstra algo");
g.shortestPathInWeightedGraph_dijkstra (0);
}
Let’s check the output of above code.
Printing edges in 2D format!!
0 3 2 6 0 0 0
0 0 0 0 6 1 0
0 2 0 0 0 0 0
0 0 0 0 0 0 2
0 0 0 0 0 0 1
0 0 0 1 0 0 5
0 0 0 0 0 0 0
========================================================================
Finding shortest path in weighted graph from Node 0 using Dijkstra algo
========================================================================
Node: 0 distance: 0 from Node: 0
Node: 1 distance: 3 from Node: 0
Node: 2 distance: 2 from Node: 0
Node: 3 distance: 5 from Node: 5
Node: 4 distance: 9 from Node: 1
Node: 5 distance: 4 from Node: 1
Node: 6 distance: 7 from Node: 3
Problems
- Dijsktra’s algorithm can also work on undirected graphs.
- Dijsktra’s algorithm to find shortest path doesn’t work correctly in case graph has negative edges.
