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 and initialize it to very high value (eg: 9999).
- Define a path array of size equal to graph node and initialize it to srcNode.
- Run a for loop of |v| – 1 times. (Shortest path of graph cannot have more than V-1 edges.)
- Iterate through each edge.
- If (distance[j] != 9999 && distance[k] > distance[j] + edges[j][k])
- Distance[k] = distance[j] + edges[j][k]
- Path[k] = j
- If (distance[j] != 9999 && distance[k] > distance[j] + edges[j][k])
- Iterate through each edge.
- Run a loop of |V| -1 times to check negative edge cycle.
- Iterate through each edge.
- If distance[k] > distance[j] + edges[j][k] then negative edge cycle exist in graph.
- Iterate through each edge.
- Print the distance and path array.
After applying the above algorithm, below is the shortest path tree for above graph.
Negative Edge Cycle
In the above graph, Node 0 and 1 has created a cycle of total weight = “-2”. Weight to reach any node will reduce if these nodes are included in the path. This means that there is no shortest path available as we can get a new shortest path by visiting this cycle once more (as it will reduce weight by “-2”).
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 (int srcNode);
};
Let’s look into the function to find shortest path using Bellman Ford’s algorithm.
/* Bellman Ford's algorithm */
void Graph::shortestPathInWeightedGraph (int srcNode)
{
int distance[m_nodes];
int path[m_nodes];
for (int i = 0; i < m_nodes; i++) {
distance[i] = 9999;
path[i] = 0;
}
distance[srcNode] = 0;
path[srcNode] = srcNode;
/* The shortest path of graph that contain V vertices, never contain more than "V-1" edges.
So we do here "V-1" iterations */
for (int i = 0; i < m_nodes-1; i++) {
for (int j = i; j < m_nodes; j++) {
for (int k = 0; k < m_nodes; k++) {
if (edges[j][k] != 0) {
//printf ("%d -- %d -- %d -- %d -- %d -- %d -- %d\n", m_nodes, i, j, k, edges[j][k], distance[j], distance[k]);
if (distance[j] != 9999 && distance[k] > distance[j] + edges[j][k]) {
distance[k] = distance[j] + edges[j][k];
path[k] = j;
}
}
}
}
}
for (int i = 0; i < m_nodes; i++) {
bool exit = false;
for (int j = 0; j < m_nodes; j++) {
if (edges[i][j] != 0 && distance[j] > distance[i] + edges[i][j]) {
cout << "Negative edge cycle exists in Graph !!!" << endl;
exit = true;
break;
}
}
if (exit)
break;
}
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.addEdgeWithWeight (1, 0, -5);
g.getEdgesIn2DFormat ();
add_header ("Finding shortest path in weighted graph from Node 0 using Bellman's Ford algo");
g.shortestPathInWeightedGraph (0);
}
Let’s check the output of above code.
Printing edges in 2D format!!
0 3 2 6 0 0 0
-5 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 Bellman's Ford algo
========================================================================
Negative edge cycle exists in Graph !!!
Node: 0 distance: -2 from Node: 1
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
