3 ms·
>Find the shortest path from one node to all other nodes in a graph That is precisely what Dijkstra's algorithm does. The limitation of that algo is that it on
by eezurr 5y ago
>Find the shortest path from one node to all other nodes in a graph
That is precisely what Dijkstra's algorithm does. The limitation of that algo is that it only finds one path from the start to each other node, not all possible paths. As a really simple example, consider a 2x2 graph:
A---B
| |
C---D
If you want to go from A to D, Dijkstra will return _either_ A-B-D or A-C-D, but not both. The "k path problem" tries to find all paths from A to D
- sgillen 5y agoAh, I see what you are saying now. Have you seen this https://stackoverflow.com/questions/2819347/dijkstras-algorithm-to-find-all-the-shortest-paths-possible https://stackoverflow.com/questions/2819347/dijkstras-algori... stack overflow post yet? It seems to be provide a way to modify Dijkstra's to do what you want? I'm not sure this is what you are looking for, but if that variant of Dijkstra's can be made to work you should probably include it as a comparison in any white paper you make!