Given a weighted undirected or directed graph with non-negative weights, you want to solve the Single Source Shortest Path problem. From a start vertex v, you want to find the shortest path from v to every other node in the graph, hence why it is called single source shortest path.
Dijkstra’s algorithm is the most common way to solve this problem. It is a greedy search problem that resembles a BFS search. We begin by having a distance array d which will end up storing the lengths of the shortest paths at the end. Initially all d[i] = infinity and d[v] = 0. We will also store a visited array denoting whether or not we have processed a certain node or not. Now the algorithm is as following:
In each step, we take the unvisited node with the smallest distance, mark it as visited, and then perform relaxations. From this unvisited node, say k, we will try to move to all adjacent edges. We will check whether d[k] + edge_weight < d[next_node]. If it improves the next distance, we will change the distance of the next node and thus we have performed a relaxation. The process should terminate once all nodes are marked or N iterations in which case the graph would be disconnected if we didn’t reach all nodes.
Naively, we can do this in O(NM) time complexity where N is the number of nodes and M is the number of edges. However, we can speed this up considerably by using a priority_queue. This implementation resembles BFS in that we repeatedly add nodes to be processed into a queue while using the priority to find the node with the smallest current distance.
| const int infinity = INT_MAX; int N; vector<vector<pair<int, int>>> adj(N+1); vector<int> dist(N+1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //priority_queue stored with smallest at the top void dijkstra(int source){ fill(dist.begin(), dist.end(), infinity); dist[source] = 0; pq.push({dist[source], source}); //stores distance, node pair and will be sorted by distance while(!pq.empty()){ auto [w, v] = pq.top(); pq.pop(); if(w != dist[v]){ //dist[v] has been relaxed an additional time, we don’t need to process this weight. continue; } for(auto [u, cost] : adj[v]){ if(cost + w < dist[u]){ //relaxing edge dist[u] = cost + w; pq.push({dist[u], u}); //add to priority_queue } } } //at the end, dist should be filled with the correct distances. } |
Negative Edge Weights
If there are negative edge weights, we can use SPFA (Shortest Path Fast Algorithm), which is an extension of bellman-ford. However, this has worst case of O(NM) but it can detect negative cycles.