Summary
A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use.
Floyd-Warshall
Shortest paths (multiple sources) in such graphs that:
- Edges are undirected or directed;
- Edges have positive or negative weights;
- No circles have negative weights;
It is actually a DP problem. We define alg[k][x][y] as the shortest path from x to y using the nodes [k, n-1].
We have f[k][x][y] = min(f[k+1][x][y], f[k+1][x][k]+f[k+1][k][y]. We can’t visit k twice since it would make the path longer than the first visit (circles are of positive weights).
As an initiation, f[n][x][y]=edge[x][y]. We noticed that the first dimension could be eliminated.
The time complexity will be O(V^3).
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i==j) alg[i][j]=0;
else if (edge[i].count(j)) alg[i][j]=edge[i][j];
else alg[i][j]=INT_MAX;
}
}
for (int k = n; k >= 1; --k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
alg[i][j] = min(alg[i][j], alg[i][k] + alg[k][j]);
}
}
}Bellman-Ford
Shortest paths (single source) in such graphs that:
- Edges are undirected or directed;
- Edges have positive or negative weights;
- Report paths not exist if there are negative cycles;
Bellman-Ford is super useful if the problem limits the number of stops in the paths.
It is a DP problem as well. We define alg[i][k] as the shortest path from src to any node i using k edges.
As an initiation, we have alg[src][0]=0 and all other values equal to INT_MAX.
We have alg[i][k]=min(alg[i][k-1], min{alg[j][k-1] + cost[j][i]}). To obtain the value of min{alg[j][k-1] + cost[j][i]}, we can simply iterate all edges.
The time complexity will be O(VE). Since at most we will use |V|-2 stops from source to destination.
// e[0] -> e[1]: costs e[2] dollars
vector<vector<int>> alg(n, vector<int>(K + 1, INT_MAX / 2));
alg[src][0] = 0;
for (int k = 1; k <= K; ++k) {
for (auto const &e : edges) {
// alg[e[1]][k] = min(alg[e[1]][k - 1], alg[e[0]][k - 1] + e[2]) is
// incorrect, since the previous edge could update alg[e[1]][k]
alg[e[1]][k] = min(alg[e[1]][k], alg[e[1]][k - 1]);
alg[e[1]][k] = min(alg[e[1]][k], alg[e[0]][k - 1] + e[2]);
}
}If we don’t need to limit the steps. An 1d table is sufficient.
vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int k = 1; k <= n; ++k) {
for (auto const &e : edges) {
if (dist[e[0]] != INT_MAX && dist[e[0]] + e[2] < dist[e[1]]) {
dist[e[1]] = dist[e[0]] + e[2];
}
}
}To detect if there are negative cycles, another loop to iterate each edge after |V| iterations could do the trick.
for (auto const &e : edges) {
if (dist[e[0]] + e[2] < dist[e[1]]) {
return NEGATIVE_CYCLE_FOUND;
}
}Dijkstra
Shortest paths (single source) in such graphs that:
- Edges are undirected or directed;
- Edges have positive weights;
Dijkstra’s algorithm uses priority queue and greedy strategy.
We use a priority queue to stores the potential nodes we could visit and its current cost. At initialization stage, we source’s direct neighbors. We greedily choose the node with lowest cost to visit.
In each iteration, the cost we get is guaranteed to be the shortest path from source to the current node, which is a property of greedy (the first visit will always have smaller cost than other costs in queue). Note that: Not like BFS, where we can mark node as visited when we push them in the queue, a node is marked as visited (gains its shortest path) only when it gets out of the queue.
We then visit the newly introduced edges regarding the current node and update the shortest path in the queue (to guarantee there are no duplicate nodes in the queue).
The size of queue will be at most O(V); each node might have at most O(V) edges; the graph has O(E) edges, we visit each node once. So the time complexity will be O((E+V)logV).
# Trick: use hash map and iterator to update the shortest path in the queue
vector<int> Dijkstra(int n, int src, unordered_map<int, unordered_map<int, int>> weight) {
// shortest path
vector<int> dist(n, INT_MAX);
// {cost, node}
set<pair<int, int>> s;
vector<iter> s_iter(n, s.end());
// initialization
s.insert({0, src});
s_iter[src] = s.begin();
dist[src] = 0;
while (!s.empty()) {
// u is the current node
auto [cost, u] = *s.begin();
s.erase(s.begin());
// get the shortest path from src to u
dist[u] = cost;
// v is the next node
for (auto const &[v, w] : weight[u]) {
// this check is a must, since if dist[v] is visited, s_iter[v] won't be valid
if (dist[v] != INT_MAX) {
continue;
}
int new_cost = cost + w;
if (s_iter[v] != s.end()) {
// update the cost in the priority queue if the new_cost is lower
if (new_cost < s_iter[v]->first) {
s.erase(s_iter[v]);
s_iter[v] = s.insert({new_cost, v}).first;
}
} else {
s_iter[v] = s.insert({new_cost, v}).first;
}
}
}
return dist;
}The above implementation works well if |E|>>|V|. Actually in many problems we have |E|≈|V|, then we could apply lazy deletion to simplify the implementation.
# Trick: lazy deletion; push extra edges into queue and delete them when they are popped out
vector<int> Dijkstra(int n, int src, unordered_map<int, unordered_map<int, int>> weight) {
// shortest path
vector<int> dist(n, INT_MAX);
// {cost, node}
set<pair<int, int>> s;
// initialization
s.insert({0, src});
s_iter[src] = s.begin();
dist[src] = 0;
while (!s.empty()) {
// u is the current node
auto [cost, u] = *s.begin();
s.erase(s.begin());
// lazy deletion
// we have visited the node before and obtained the smallest cost
if (dist[u] < INT_MAX) {
continue;
}
// get the shortest path from src to u
dist[u] = cost;
// v is the next node
for (auto const &[v, w] : weight[u]) {
int new_cost = cost + w;
// optional
if (dist[v] < INT_MAX) {
continue;
}
s.insert({new_cost, v}).first;
}
}
return dist;
}