Shortest Path Algorithm

Bellman-Ford Algorithm

Given a weighted graph and a source vertex src, the task is to find the shortest path distances from src to all other vertices. The graph may contain negative weight edges. The Bellman-Ford algorithm solves this problem and also detects negative weight cycles (cycles whose total weight is negative).

The Bellman-Ford algorithm should be preferred when the graph may contain negative edges. Dijkstra's algorithm is faster for non-negative weights (for example O(V log V) with Fibonacci heap or O(E log V) with a binary heap and adjacency list), but it does not handle negative edge weights. Bellman-Ford is simpler to implement and is suitable for some distributed settings, but its time complexity is O(V·E), which is larger than Dijkstra's for sparse graphs.

Problem statement

Input: A weighted directed graph (weights may be negative) and a source vertex src.

Output: Shortest distances from src to every vertex. If a negative weight cycle is reachable from src, report that a negative weight cycle exists and do not report finite shortest distances for vertices affected by that cycle.

Algorithm

1. Initialise an array dist[] of size |V| with all entries as infinity (use a large sentinel, e.g., INT_MAX), and set dist[src] = 0.
2. Relax all edges repeatedly. Repeat the following process exactly |V| - 1 times:

   For every edge (u, v) with weight w, if dist[u] ≠ ∞ and dist[u] + w < dist[v], then set dist[v] = dist[u] + w.

3. Check for negative weight cycles:

   For every edge (u, v) with weight w, if dist[u] ≠ ∞ and dist[u] + w < dist[v], then the graph contains a negative weight cycle reachable from the source.

How the algorithm works (intuition and correctness)

The algorithm uses a bottom-up dynamic programming idea. After the i-th full iteration of edge relaxations, all shortest paths that use at most i edges will have been found. Any simple path in a graph with |V| vertices has at most |V| - 1 edges. Therefore, after |V| - 1 iterations, shortest paths (that do not use cycles) are finalised, provided there is no negative weight cycle. If an extra iteration still shortens any distance, that indicates a reachable negative weight cycle.

Example

Consider an example graph with source vertex 0. Initialise distances to ∞ except dist[0] = 0. The graph has 5 vertices, so every edge must be relaxed 4 times.

Suppose edges are processed in this order: (B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D). The table below (illustrative) shows the distances after successive relaxations. The first row is the initial distances. The second row shows distances after the first group of edges are processed; subsequent rows show updates as more edges are processed.

The first iteration guarantees correct shortest distances for paths with at most one edge. After completing two iterations, all shortest paths with at most two edges are obtained. Since the example's distances stabilise by the second iteration, further iterations do not change distances.

Implementation (C / C++)

#include <stdio.h> #include <stdlib.h> #include <limits.h> /* a structure to represent a weighted edge in graph */ struct Edge { int src, dest, weight; }; /* a structure to represent a connected, directed and weighted graph */ struct Graph { /* V -> Number of vertices, E -> Number of edges */ int V, E; /* graph is represented as an array of edges */ struct Edge* edge; }; struct Graph* createGraph(int V, int E) { struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); graph->V = V; graph->E = E; graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge)); return graph; } /* Utility function to print the solution */ void printArr(int dist[], int n) { printf("Vertex Distance from Source
"); for (int i = 0; i < n; ++i) printf("%d \t %d
", i, dist[i]); } /* The main function that finds shortest distances from src to all other vertices using Bellman-Ford algorithm. The function also detects negative weight cycle */ void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = graph->E; int dist[V]; /* Step 1: Initialize distances from src to all other vertices as INFINITE */ for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; /* Step 2: Relax all edges |V| - 1 times. */ for (int i = 1; i <= V-1; i++) { for (int j = 0; j < E; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int weight = graph->edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } /* Step 3: check for negative-weight cycles. */ for (int i = 0; i < E; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int weight = graph->edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { printf("Graph contains negative weight cycle
"); return; } } printArr(dist, V); return; } /* Driver program to test above functions */ int main() { int V = 5; /* Number of vertices in graph */ int E = 8; /* Number of edges in graph */ struct Graph* graph = createGraph(V, E); /* add edge 0-1 (or A-B in above figure) */ graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = -1; /* add edge 0-2 (or A-C in above figure) */ graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 4; /* add edge 1-2 (or B-C in above figure) */ graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].weight = 3; /* add edge 1-3 (or B-D in above figure) */ graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].weight = 2; /* add edge 1-4 (or B-E in above figure) */ graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].weight = 2; /* add edge 3-2 (or D-C in above figure) */ graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].weight = 5; /* add edge 3-1 (or D-B in above figure) */ graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].weight = 1; /* add edge 4-3 (or E-D in above figure) */ graph->edge[7].src = 4; graph->edge[7].dest = 3; graph->edge[7].weight = -3; BellmanFord(graph, 0); return 0; } 

Output:

Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1 

Notes and practical points

• Negative edge weights occur in many applications. They may represent gains or reductions rather than costs.
• Bellman-Ford is more suitable than Dijkstra's when negative weights are present. In distributed implementations the edge-oriented relaxation can be convenient.
• To reconstruct shortest paths, maintain a predecessor array parent[]. When you relax edge (u, v), set parent[v] = u if you update dist[v]. If a negative cycle exists, predecessor information for vertices reachable through the cycle does not reflect a well-defined shortest simple path.
• Optimisations: if an entire iteration performs no distance updates, you can stop early. The Shortest Path Faster Algorithm (SPFA) is a queue-based refinement that often performs better on many graphs, but it has worst-case exponential behaviour and is not guaranteed to be faster in theory.

Exercise

1. The standard Bellman-Ford algorithm reports shortest path only if there is no negative weight cycles. Modify it so that it reports minimum distances even if there is a negative weight cycle.
2. Can we use Dijkstra's algorithm for shortest paths for graphs with negative weights - one idea can be: calculate the minimum weight value, add a positive value (equal to absolute value of minimum weight value) to all weights and run Dijkstra's algorithm for the modified graph. Will this algorithm work?

Dijkstra's shortest path algorithm

Given a weighted graph with non-negative edge weights and a source vertex, find the shortest path distances from the source to all other vertices. Dijkstra's algorithm solves this efficiently when all edge weights are non-negative.

Idea and relation to Prim's algorithm

Dijkstra's algorithm is similar to Prim's algorithm for minimum spanning tree. It constructs a shortest path tree (SPT) rooted at the source by selecting at each step the vertex with the minimum tentative distance from the source and finalising it. Two sets are maintained: one contains vertices whose shortest distance from the source is final (the SPT set), the other contains vertices not yet finalised.

Algorithm (detailed steps)

1. Create a boolean array sptSet[] to track vertices included in shortest path tree. Initially all entries are false.
2. Create an array dist[] and initialize all values as infinity; set dist[source] = 0.
3. While sptSetdoes not include all vertices:

   Pick a vertex u not in sptSet with the minimum dist[u], include u in sptSet, and update distances of all adjacent vertices v of u: if dist[v] > dist[u] + weight(u, v), set dist[v] = dist[u] + weight(u, v) and update parent information if building paths.

Example

Start with source 0. Initially dist = {0, INF, INF, INF, INF, INF, INF, INF, INF}. The SPT set is empty. Pick vertex 0 (dist 0), finalise it, and relax its neighbours. Repeat picking the smallest tentative vertex outside the SPT and relaxing edges; the sequence of chosen vertices and the evolving tree produce the shortest path tree shown below.

After first step, neighbours of 0 (vertices 1 and 7) get finite tentative distances 4 and 8 respectively. The set of finalised vertices and current tentative distances can be visualised as the algorithm proceeds.

Vertex 1 is chosen next; its relaxations update its neighbours.

Vertex 7 is chosen later and its relaxations update vertices 6 and 8.

Continuing until all vertices are finalised yields the final shortest path tree.

Implementation (C / C++) - adjacency matrix version

#include <stdio.h> #include <limits.h> #include <stdbool.h> #define V 9 /* Number of vertices in the graph */ /* Utility function to find the vertex with minimum distance value, from the set of vertices not yet included in shortest path tree */ int minDistance(int dist[], bool sptSet[]) { int min = INT_MAX, min_index = -1; for (int v = 0; v < V; v++) if (!sptSet[v] && dist[v] <= min) { min = dist[v]; min_index = v; } return min_index; } /* Utility function to print the constructed distance array */ void printSolution(int dist[], int n) { printf("Vertex Distance from Source
"); for (int i = 0; i < V; i++) printf("%d \t %d
", i, dist[i]); } /* Function that implements Dijkstra's single source shortest path algorithm for a graph represented using adjacency matrix representation */ void dijkstra(int graph[V][V], int src) { int dist[V]; /* dist[i] will hold the shortest distance from src to i */ bool sptSet[V]; /* sptSet[i] will be true if vertex i is included in SPT */ /* Initialize all distances as INFINITE and sptSet[] as false */ for (int i = 0; i < V; i++) { dist[i] = INT_MAX; sptSet[i] = false; } /* Distance of source vertex from itself is always 0 */ dist[src] = 0; /* Find shortest path for all vertices */ for (int count = 0; count < V-1; count++) { /* Pick the minimum distance vertex from the set of vertices not yet processed */ int u = minDistance(dist, sptSet); /* Mark the picked vertex as processed */ sptSet[u] = true; /* Update dist value of the adjacent vertices of the picked vertex */ for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } /* print the constructed distance array */ printSolution(dist, V); } /* driver program to test above function */ int main() { int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {8, 11, 0, 0, 0, 2, 0, 1, 6}, {0, 0, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0} }; dijkstra(graph, 0); return 0; } 

Output:

Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14 

Notes and practical points

• The provided implementation computes only distances. To reconstruct actual shortest paths, maintain a parent[] array and update it when a distance is relaxed.
• The adjacency matrix code has time complexity O(V^2). If the graph is represented with adjacency lists and a binary heap (priority queue) is used, the complexity becomes O((V + E) log V), often written as O(E log V) for connected graphs; with a Fibonacci heap it can be reduced to O(E + V log V).
• Dijkstra's algorithm does not work with negative weight edges. If any edge weight is negative, Dijkstra's greedy selection of the current minimum distance vertex may become invalid.
• If interest is only in the shortest distance to a single target, you may stop the algorithm early when the target vertex is finalised.

Comparison: Bellman-Ford vs Dijkstra

• Edge weights: Dijkstra requires non-negative edge weights; Bellman-Ford supports negative weights and detects negative cycles.
• Time complexity: Dijkstra with a good priority queue is typically faster on sparse graphs (O(E log V)). Bellman-Ford runs in O(V·E).
• Use cases: Use Bellman-Ford when negative weights or cycle detection is needed. Use Dijkstra for faster computation on non-negative graphs.
• Path reconstruction: Both algorithms can reconstruct paths by maintaining parent/predecessor pointers during relaxation.