2
我目前使用Dijkstra算法尋找最短路徑。這個算法給了我最好的最短路徑,但是我想有2條或更多的路徑。我怎樣才能做到這一點?使用Dijkstra的多條最短路徑
算法如下:
public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
你所說的2個或更多PA指什麼部份?如果最短路徑的長度爲「x」,那麼是否需要所有長度爲「x」的路徑?或者你想要2個最短的路徑(第二個路徑可能是'> x')? – 2013-04-28 12:21:08
https://code.google.com/p/k-shortest-paths/ – 2013-04-28 13:05:32
http://en.wikipedia.org/wiki/K_shortest_path_routing – 2013-04-28 13:06:10