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. <\/p>\n\n\n\n
Shortest paths (multiple sources) in such graphs that: <\/p>\n\n\n\n
It is actually a DP problem. We define We have As an initiation, The time complexity will be Shortest paths (single source) in such graphs that: <\/p>\n\n\n\n Bellman-Ford is super useful if the problem limits the number of stops in the paths. <\/p>\n\n\n\n It is a DP problem as well. We define As an initiation, we have We have The time complexity will be If we don’t need to limit the steps. An 1d table is sufficient. <\/p>\n\n\n\n To detect if there are negative cycles, another loop to iterate each edge after Shortest paths (single source) in such graphs that: <\/p>\n\n\n\n Dijkstra’s algorithm uses 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<\/strong> choose the node with lowest cost to visit. <\/p>\n\n\n\n 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<\/strong> (the first visit will always have smaller cost than other costs in queue). Note that<\/strong>: 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. <\/p>\n\n\n\n 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). <\/p>\n\n\n\n The size of queue will be at most The above implementation works well if 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: It is actually a DP problem. We define alg[k][x][y] as the shortest path from x to y using the…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,66],"tags":[],"class_list":["post-1288","post","type-post","status-publish","format-standard","hentry","category-alg","category-graph-alg"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1288","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1288"}],"version-history":[{"count":34,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1288\/revisions"}],"predecessor-version":[{"id":1686,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1288\/revisions\/1686"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1288"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1288"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1288"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}alg[k][x][y]<\/code> as the shortest path from x<\/code> to y<\/code> using the nodes [k, n-1]<\/code>. <\/p>\n\n\n\nf[k][x][y] = min(f[k+1][x][y], f[k+1][x][k]+f[k+1][k][y]<\/code>. We can’t visit k twice since it would make the path longer than the first visit (circles are of positive weights). <\/p>\n\n\n\nf[n][x][y]=edge[x][y]<\/code>. We noticed that the first dimension could be eliminated. <\/p>\n\n\n\nO(V^3)<\/code>.<\/p>\n\n\n\nfor (int i = 1; i <= n; ++i) {\n for (int j = 1; j <= n; ++j) {\n if (i==j) alg[i][j]=0;\n else if (edge[i].count(j)) alg[i][j]=edge[i][j];\n else alg[i][j]=INT_MAX;\n }\n}\nfor (int k = n; k >= 1; --k) {\n for (int i = 1; i <= n; ++i) {\n for (int j = 1; j <= n; ++j) {\n alg[i][j] = min(alg[i][j], alg[i][k] + alg[k][j]);\n }\n }\n}<\/code><\/pre>\n\n\n\nBellman-Ford<\/h2>\n\n\n\n
\n
alg[i][k]<\/code> as the shortest path from src<\/code> to any node i<\/code> using k<\/code> edges. <\/p>\n\n\n\nalg[src][0]=0<\/code> and all other values equal to INT_MAX<\/code>.<\/p>\n\n\n\nalg[i][k]=min(alg[i][k-1], min{alg[j][k-1] + cost[j][i]})<\/code>. To obtain the value of min{alg[j][k-1] + cost[j][i]}<\/code>, we can simply iterate all edges. <\/p>\n\n\n\nO(VE)<\/code>. Since at most we will use |V|-2<\/code> stops from source to destination. <\/p>\n\n\n\n\/\/ e[0] -> e[1]: costs e[2] dollars\nvector<vector<int>> alg(n, vector<int>(K + 1, INT_MAX \/ 2));\nalg[src][0] = 0;\n\nfor (int k = 1; k <= K; ++k) {\n for (auto const &e : edges) {\n\/\/ alg[e[1]][k] = min(alg[e[1]][k - 1], alg[e[0]][k - 1] + e[2]) is \n\/\/ incorrect, since the previous edge could update alg[e[1]][k]\n alg[e[1]][k] = min(alg[e[1]][k], alg[e[1]][k - 1]);\n alg[e[1]][k] = min(alg[e[1]][k], alg[e[0]][k - 1] + e[2]);\n }\n}<\/code><\/pre>\n\n\n\nvector<int> dist(n, INT_MAX);\ndist[src] = 0;\n\nfor (int k = 1; k <= n; ++k) {\n for (auto const &e : edges) {\n if (dist[e[0]] != INT_MAX && dist[e[0]] + e[2] < dist[e[1]]) {\n dist[e[1]] = dist[e[0]] + e[2];\n }\n }\n}<\/code><\/pre>\n\n\n\n|V|<\/code> iterations could do the trick. <\/p>\n\n\n\nfor (auto const &e : edges) {\n if (dist[e[0]] + e[2] < dist[e[1]]) {\n return NEGATIVE_CYCLE_FOUND;\n } \n}<\/code><\/pre>\n\n\n\nDijkstra<\/h2>\n\n\n\n
\n
priority queue<\/code> and greedy<\/code> strategy. <\/p>\n\n\n\nO(V)<\/code>; each node might have at most O(V)<\/code> edges; the graph has O(E)<\/code> edges, we visit each node once. So the time complexity will be O((E+V)logV)<\/code>.<\/p>\n\n\n\n# Trick: use hash map and iterator to update the shortest path in the queue\n\nvector<int> Dijkstra(int n, int src, unordered_map<int, unordered_map<int, int>> weight) {\n \/\/ shortest path\n vector<int> dist(n, INT_MAX);\n \/\/ {cost, node}\n set<pair<int, int>> s;\n vector<iter> s_iter(n, s.end());\n\n \/\/ initialization\n s.insert({0, src});\n s_iter[src] = s.begin();\n dist[src] = 0;\n\n while (!s.empty()) {\n \/\/ u is the current node\n auto [cost, u] = *s.begin();\n s.erase(s.begin());\n\n \/\/ get the shortest path from src to u\n dist[u] = cost;\n\n \/\/ v is the next node\n for (auto const &[v, w] : weight[u]) {\n \/\/ this check is a must, since if dist[v] is visited, s_iter[v] won't be valid\n if (dist[v] != INT_MAX) {\n continue;\n }\n int new_cost = cost + w;\n if (s_iter[v] != s.end()) {\n \/\/ update the cost in the priority queue if the new_cost is lower\n if (new_cost < s_iter[v]->first) {\n s.erase(s_iter[v]);\n s_iter[v] = s.insert({new_cost, v}).first;\n }\n } else {\n s_iter[v] = s.insert({new_cost, v}).first;\n }\n }\n }\n return dist;\n}<\/code><\/pre>\n\n\n\n|E|>>|V|<\/code>. Actually in many problems we have |E|\u2248|V|<\/code>, then we could apply lazy deletion to simplify the implementation. <\/p>\n\n\n\n# Trick: lazy deletion; push extra edges into queue and delete them when they are popped out\nvector<int> Dijkstra(int n, int src, unordered_map<int, unordered_map<int, int>> weight) {\n \/\/ shortest path\n vector<int> dist(n, INT_MAX);\n \/\/ {cost, node}\n set<pair<int, int>> s;\n\n \/\/ initialization\n s.insert({0, src});\n s_iter[src] = s.begin();\n dist[src] = 0;\n\n while (!s.empty()) {\n \/\/ u is the current node\n auto [cost, u] = *s.begin();\n s.erase(s.begin());\n \n \/\/ lazy deletion\n \/\/ we have visited the node before and obtained the smallest cost\n if (dist[u] < INT_MAX) {\n continue;\n }\n\n \/\/ get the shortest path from src to u\n dist[u] = cost;\n\n \/\/ v is the next node\n for (auto const &[v, w] : weight[u]) {\n int new_cost = cost + w;\n \/\/ optional\n if (dist[v] < INT_MAX) {\n continue;\n }\n s.insert({new_cost, v}).first;\n }\n }\n return dist;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"