| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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?
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
It is called Minimal Spanning Tree and Prim's algorithm
It is a shortest path problem with weight $$$(10^{100})^w$$$
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)
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 .
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.
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 .
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$$$.
So that modified Dijkstra is minimum spanning tree problem in this case which i mentioned in my first comment.