multiples chemins les plus courts en utilisant Dijkstra

Question

J'utilise actuellement l'algorithme de Dijkstra pour trouver le plus court chemin. Cet algorithme me donne le meilleur chemin le plus court mais je veux avoir 2 chemins ou plus. Comment puis-je atteindre cet objectif?

algorithme est le suivant:

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); 
     } 
      } 
     } 
    } 

Answer 1

Il est le Yen Top K algorithme de chemin le plus court qui utilise Dijkstra pour calculer la trajectoire optimale, après qu'il utilise Dijkstra pour calculer la deuxième voie la plus optimale, etc.

J'ai trouvé une implémentation Java pour que ici: https://github.com/yan-qi/k-shortest-paths-java-version/tree/master/src/main/java/edu/asu/emit/algorithm/graph/shortestpaths

Hope qui aide