CODEWITHSUNDEEP
algorithmweighted-graph
Alviss Min
Alviss Min

Reputation: 79

Weighted graph fatness algorithm

Consider a connected weighted directed graph G = (V, E, w). The fatness of a path P is maximum weight of any edge in P.

How to find the minimum possible fatness of the graph? Could Dijkstra's algorithm be used to find the minimum fatness?

Upvotes: 1

Views: 423

Answers (1)

Prateek Mirdha
Prateek Mirdha

Reputation: 67

Actually you are thinking in right direction but Djkstra's algo will only let you know minimum fatness of a path from a single source(i.e. single source shortest path), but to find fatness for whole graph you need to find shortest path from all nodes to every other node, so you need to apply Floyd–Warshall algorithm.

Hope it helps.

Upvotes: 1

Related Questions