CODEWITHSUNDEEP
algorithmgraphtraversalshortest-pathdijkstra
oirampok
oirampok

Reputation: 11

Flood modelling (Modifying Dijkstra's to work with a graph where the weight of a path is the maximum weight of its edges.)

Im trying to program a flood modelling program.

To find the lowest weight path from a start vertex to a vertex, we would intuitively use Dijkstra's. What if the weight of a path is now the maximum weight of its edges? Could we modify Dijkstra's to work with this graph?

https://i.sstatic.net/YtQU4.png

Upvotes: 1

Views: 46

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

You can use Prim's algorithm to start generating a minimum spanning tree at your source vertex, and stop when you get to the target vertex.

https://en.wikipedia.org/wiki/Prim%27s_algorithm

Upvotes: 1

Related Questions