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开发者_StackOverflow中文版] 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?

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(E²) 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}).

You can solve this easily by modifying Dijkstra's to calculate maximum bandwidth to all other vertices.

You do not need to initialize the start vertex to -1.

Algorithm: Maximum Bandwidth(G,a)

Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished     vertex a of G

Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u.


Initialize empty queue Q;
Start = a;
for each vertex u of G do,
   D[u] = 0;

for all vertices z adjacent to Start do{                              ---- 1

 If D[Start] => D[z] && w(start, z) > D[z] {
    Q.enqueue(z);
    D[z] = min(D[start], D[z]);
  }
}
If Q!=null {
   Start = Q.dequeue;
   Jump to 1

}

else
  finish();

This may not be the most efficient way to calculate the bandwidth, but its what I could think of for now.

calculating flow may be more applicable, however flow allows for multiple paths to be used.

Just invert the edge weights. That is, if the edge weight is d, consider it instead as d^-1. Then do Dijkstra's as normal. Initialize all distances to infinity as normal.

You can use Dijkstra's algorithm to find a single longest path but since you only have two switch centers I don't see why you need to visit each node as in Dijkstra's. There is most likes a more optimal way of going this, such as a branch and bound algorithm.

Can you adjust some of the logic in algorithm AllPairsShortestPaths(Floyd-Warshall)? http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm

Initialize unconnected edges to negative infinity and instead of taking the min of the distances take the max?