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?
1
votes
what is the fatness of a graph? you have defined it for paths but not graphs
– m7mdbadawy
Do you search for a path under specific constraints? If there are no constraints, would an edge of minimum weight be a solution?
– Codor
the graph has alot of paths, basically what i need to find out is the path which has the least weight.
– Alviss Min
1 Answers
1
votes
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.
