AjaySabarish's blog

By AjaySabarish, history, 3 years ago, In English

Let's say we have a Graph, with N nodes and M edges, each edge has a weight associated with it, now we have to find the minimum possible, maximum edge weight in a path.

Does Dijkstra work for this scenario?

Sample problem https://leetcode.com/problems/path-with-minimum-effort/

Dijkstra works for this, but I have no idea why, can anyone help me with proof or at least an intuitive idea?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

This problem is closely related to the following problem (more precisely, it's the bottleneck shortest problem which is equivalent to the following): https://en.wikipedia.org/wiki/Widest_path_problem

»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

It is called Minimal Spanning Tree and Prim's algorithm

»
3 years ago, # |
  Vote: I like it +118 Vote: I do not like it

It is a shortest path problem with weight $$$(10^{100})^w$$$

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Yes, it works and for a very similar reason as usual Dijkstra. Search for some proof that Dijkstra works and you should be able to adjust it easily.

Key property for the fact that Dijkstra works on graphs with nonnegative weights is that if you append an edge to some path then this longer path will not have smaller weight. This property is true both for weight of a path defined as a sum of edges (when edges are nonnegative) and defined as a heaviest edge on it (when edges are arbitrary reals)

»
3 years ago, # |
Rev. 3   Vote: I like it -44 Vote: I do not like it

Dijkstra won't work directly here . Take following undirected graph , n=4 , m=4 and edges,weight = {1,2,1},{2,3,1},{3,4,1},{1,4,2} . Dijkstra would give the path 1->4 because it's length is 2 whereas path for solution will be 1->2->3->4 because maximum edge length here is 1.

So we can use prim's algorithms which is just slightly different from Dijkstra. Following is proof why prim's algorithm will find out solution to your problem (You need to read prims algorithm first to understand the proof) :

Suppose we need to reach from node $$$1$$$ to node $$$n$$$ . Suppose prims algorithm provides path say $$$A$$$ and we argue there exist another path $$$B$$$ in which maximum weight edge has less value compared to that in $$$A$$$.

But then if you see prims algorithm then all weights which are smaller will be chosen first i.e all edges in path $$$B$$$ will be chosen before the maximum weight edge in path $$$A$$$.Hence contradiction .

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The accumulator function for computing the "path length" in this problem is not the sum function; it's the max function, so your example doesn't seem to work. As pointed out above, the only thing Dijkstra's algorithm really cares about is that the "path length" never decreases upon adding an edge.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      In the blog it's mentioned "Dijkstra" , if we follow the Dijkstra algorithm won't be the path 1->4 will chosen because total length is 2 , whereas in path 1->2->3->4 total length is 3 ?

      But if we use prims algorithm , edges 1->2,2->3,3->4 will be chosen because that is the minimum spanning tree in this case . Also that is the solution to the problem posted in blog .

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If the shortest path from the root $$$u$$$ to the vertex $$$v$$$ is $$$u = u_1 \to \cdots \to u_k = v$$$, then the shortest path from $$$u$$$ to $$$v$$$ in the usual sense has path length $$$w(u_1, u_2) + \cdots + w(u_{k-1}, u_k)$$$. However, in this case, the path length is defined as $$$\max(w(u_1, u_2), \dots, w(u_{k-1}, u_k))$$$.

        In the update step, you check whether taking a path through a vertex $$$v$$$ (whose cost, in this case, is computed using $$$\max$$$) results in a decrease in the distance (defined using path length) of the vertex at the other end of the edge or not. In that sense, Dijkstra works, and gives the path $$$1 \to 2 \to 3 \to 4$$$.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -38 Vote: I do not like it

          So that modified Dijkstra is minimum spanning tree problem in this case which i mentioned in my first comment.