{"id":488,"date":"2007-08-10T16:33:00","date_gmt":"2007-08-10T16:33:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/08\/10\/shortest-paths-and-greedy-relaxation\/"},"modified":"2007-08-10T16:33:00","modified_gmt":"2007-08-10T16:33:00","slug":"shortest-paths-and-greedy-relaxation","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/08\/10\/shortest-paths-and-greedy-relaxation\/","title":{"rendered":"Shortest Paths and Greedy Relaxation"},"content":{"rendered":"

Another really fun and fundamental weighted graph problem is the shortest path<\/em> problem. The
\nquestion in: given a connected weighted graph G, what is the shortest path between two vertices
\nv and w in G?<\/p>\n

<\/p>\n

To be precise, the weight of a path is just the sum of the weight of the edges that make up
\nthe path. The shortest path between two vertices is the path with minimum weight.<\/p>\n

There are a ton of solutions to this problem. I’m going to show one of the easiest to understand ones, which is Djikstra’s algorithm. Djikstra’s algorithm for the shortest path combines two very interesting
\nalgorithmic techniques: greediness, and relaxation. We’ve already talked about greediness in the context
\nof the minimum spanning tree: a greedy algorithm is an algorithm which works by aggressively picking
\noptimum sub-values, and building the result from them. Relaxation is an algorithmic technique where
\nyou start with a maximum value, and attempt to reduce it. The easiest way to understand relaxation
\nis by metaphor: suppose you want to find the optimal arrangement of a bunch of pegs connected by springs. A relaxation technique basically moves one peg in each step in a way that reduces the tension in at least one spring without increasing the tension in any of the others. So you’re continually relaxing<\/em> the tension in the springs, until you can’t relax it any more.<\/p>\n

In Djikstra’s algorithm, you have a graph G=(V,E,W), and you want to find the shortest path
\nbetween two vertices a and b. You create a table dist(x) of the minimum distance from a to every vertex in V so that dist(x) is the distance from a to x, and you set the initial value of dist(a) to 0,
\nthe initial value of dist(x) for all other vertices in E to infinity; and you create a priority list of vertices, ordered by their distance from a.<\/p>\n

Then, in each step, you look for the vertex n in E that has the smallest<\/em> value of
\ndist(n), and you remove that vertex from the priority list. Then, for each vertex m that is adjacent to n, if the path from a to m through n is shorter
\nthan dist(m), set dist(m) = dist(n) + W(n,m). (This is called relaxing<\/em> the path from a to m.)\n<\/p>\n

When you get to the point that the next vertex selected in the priority list is b, then you’re done – you know the shortest path.<\/p>\n

In pseudo-code:<\/p>\n

\ndef shortestPath(G,a,b):\ndist = Map from vertices(G) to distance\nprev = Map from vertices(G) to vertices(G)\nfor x in vertices(G):\nif x == a:\ndist[x] = 0\nelse:\ndist[x] = ∞\nend\npriorityList = vertices(G) ordered by distance from a\nfor closest = priorityList.nextVertex() != b:\nfor v adjacent to closest:\nif dist[v] < dist(closest) + weight(closest,v):\ndist[v] = dist(closest) + weight(closest,v)\nprev[v] = closest\nend\nend\nend\n<\/pre>\n
 When the algorithm terminates, you just trace back through prev to get the shortest path from a to b.\n<\/p>\n
 So what’s the complexity of this?<\/p>\n
    \n
  •  In the worst case, b could be the last vertex extracted from the priority list, in which case
    \nwe would end up running the outer loop once for each vertex. So there’s a maximum of N iterations
    \nof that loop.<\/li>\n
  •  In the inner loop, we need to look at every edge from the selected vertex. That’s O(E). <\/li>\n
  •  To re-order the priority list after removing an element from it takes, at most, N steps.<\/li>\n<\/ul>\n
     So, we’re looking at O(|V|2<\/sup>|E|).<\/p>\n
     That’s not the best we can do; by adopting some hairy data structures for the priority queue,
    \nwe can reduce the running time to O(|V|log|V||E|). But the structures to do that have a pretty high
    \nconstants, so they only really pay off for large, sparse graphs.<\/p>\n
     Let’s trace through an example. Suppose we want to find the shortest path from A to M in the following graph.<\/p>\n
    \"shortest-path-ex.png\"<\/p>\n
     First, we set all weights to infinity, except A to A, all predecessors to empty, and we’ll compute
    \nthe weights for the priority list. The following shows the initial state of all of these.<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\n0<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
    \tNow, we pick something off  the priority list. The highest priority is 0, for A itself. So we pick A, and
    \nfrom A, we can give distances and priorities to B and D.<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n3<\/td>\n∞<\/td>\n5<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\nA<\/td>\n–<\/td>\nA<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\nX<\/td>\n3<\/td>\n–<\/td>\n5<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
     Now, we greedily pick the node with the lowest priority value – B and process its edges.<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n3<\/td>\n∞<\/td>\n5<\/td>\n14<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\nA<\/td>\n–<\/td>\nA<\/td>\nB<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\nX<\/td>\nX<\/td>\n–<\/td>\n5<\/td>\n14<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
     Next lowest priority is D, with 5.<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n3<\/td>\n12<\/td>\n5<\/td>\n14<\/td>\n13<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\nA<\/td>\nE<\/td>\nA<\/td>\nB<\/td>\nD<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\nX<\/td>\nX<\/td>\n12<\/td>\nX<\/td>\n14<\/td>\n13<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
     Next is C, with priority 12. C gives us a new path to F, but it’s a path of length 14, which is longer than the path we already
    \nfound.<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n3<\/td>\n12<\/td>\n5<\/td>\n14<\/td>\n13<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\nA<\/td>\nE<\/td>\nA<\/td>\nB<\/td>\nD<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\n14<\/td>\n13<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
     Next is F, with priority 13. Then there’s a tie, so we pick one randomly, and do E. Then G. After those steps, the table looks like:<\/p>\n\n\n\n\n\n
    <\/th>\nA<\/th>\nB<\/th>\nC<\/th>\nD<\/th>\nE<\/th>\nF<\/th>\nG<\/th>\nH<\/th>\nI<\/th>\nJ<\/th>\nK<\/th>\nL<\/th>\nM<\/th>\n<\/tr>\n
    Dist<\/td>\n0<\/td>\n3<\/td>\n12<\/td>\n5<\/td>\n14<\/td>\n13<\/td>\n14<\/td>\n18<\/td>\n17<\/td>\n18<\/td>\n∞<\/td>\n∞<\/td>\n∞<\/td>\n<\/tr>\n
    Pred<\/td>\n–<\/td>\nA<\/td>\nE<\/td>\nA<\/td>\nB<\/td>\nD<\/td>\nF<\/td>\nE<\/td>\nE<\/td>\nG<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
    Priority<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\nX<\/td>\n18<\/td>\n17<\/td>\n18<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n<\/table>\n
     It continues on in the same way, until we get the result   ADFGJKM with a total length of 26.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Another really fun and fundamental weighted graph problem is the shortest path problem. The question in: given a connected weighted graph G, what is the shortest path between two vertices v and w in G?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-488","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7S","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/488","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=488"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/488\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=488"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=488"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=488"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}