Dijkstra's algorithm to find most weighted path
I just want to make sure this would work. Could you find the greatest path using Dijkstra's algorithm? Would you have to initialize the distance to something like -1 first and then change the relax subroutine to check if it's greater?
This is for a problem that will not have any negative weights.
This is actually the problem:
Suppose you are given a diagram of a telephone network, which is a graph G whose vertices represent switches centers, and whose edges represent communication lines between two centers. The edges are marked by their bandwidth of its lowest bandwidth edge. Give an algorithm that, given a diagram and two switches centers a and b, will output the maximum bandwidth of a path between a and b.
Would this work?
EDIT:
I did find this:
Hint: The basic subroutine will be very similar to the subroutine Relax in Dijkstra. Assume that we have an edge (u, v). If min{d[u],w(u, v)} > d[v] then we should update d[v] to min{d[u],w(u, v)} (because the path from a to u and then to v has bandwidth min{d[u],w(u, v)}, which is more than the one we have currently).
Not exactly sure what that's suppose to mean though since all distance are infinity on initialization. So, i don't know how this would work. any clues?
Answer
I'm not sure Djikstra's is the way to go. Negative weights do bad, bad things to Djikstra's.
I'm thinking that you could sort by edge weight, and start removing the lowest weight edge (the worst bottleneck), and seeing if the graph is still connected (or at least your start and end points). The point at which the graph is broken is when you know you took out the bottleneck, and you can look at that edge's value to get the bandwidth. (If I'm not mistaken, each iteration takes O(E) time, and you will need O(E) iterations to find the bottleneck edge, so this is an O(E2) algorithm.
Edit: you have to realize that the greatest path isn't necessarily the highest bandwidth: you're looking to maximize the value of min({edges in path}), not sum({edges in path}).