Modifier l'Algorithme de Dijkstra pour obtenir le plus court Chemin Entre Deux Nœuds

Donc, j'ai vu des questions similaires à cela, mais pas tout à fait exactement ce que je cherche. J'ai besoin de modifier l'Algorithme de Dijkstra pour revenir le plus court chemin entre un sommet S (source) et un sommet X (destination). Je crois que j'ai compris de quoi faire, mais j'aimerais un peu d'aide. Voici le pseudo-code que j'ai modifié.

 1  function Dijkstra(Graph, source, destination):
 2      for each vertex v in Graph:                                //Initializations
 3          dist[v] := infinity ;                                  //Unknown distance function from 
 4                                                                 //source to v
 5          previous[v] := undefined ;                             //Previous node in optimal path
 6      end for                                                    //from source
 7      
 8      dist[source] := 0 ;                                        //Distance from source to source
 9      Q := the set of all nodes in Graph ;                       //All nodes in the graph are
10                                                                 //unoptimized - thus are in Q
11      while Q is not empty:                                      //The main loop
12          u := vertex in Q with smallest distance in dist[] ;    //Start node in first case
13          remove u from Q ;
14          if dist[u] = infinity:
15              break ;                                            //all remaining vertices are
16          end if                                                 //inaccessible from source
17          
18          for each neighbor v of u:                              //where v has not yet been 
19                                                                 //removed from Q.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                  //Relax (u,v,a)
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           //Reorder v in the Queue
25              end if
26          end for
27      end while
28  return dist[destination];

Le code a été prise à partir de Wikipedia et modifié le: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Ne ce look correct?

Pourquoi auriez-vous besoin de le modifier? C'est exactement ce qu'il fait. Lorsque vous définissez toutes les bord des poids de 1.
C'est le code que j'ai déjà modifié. Donc, si il fonctionne très bien.
Aussi, comme le sommet de sélection de Dijkstra est gourmand, dès que vous obtenez "u = destination", vous pouvez interrompre la boucle.
qui fait beaucoup de sens. Je vous remercie.

OriginalL'auteur csnate | 2012-11-19

  1. 4

    De l'algorithme de Dijkstra n'a pas besoin d'être modifiée, elle est une des paires plus court chemin algorithme. Il semble que vous essayez de trouver le plus court chemin entre deux nœuds spécifiques - Dijkstra gère cela très bien.

    Si vous voulez quelque chose qui est conçu spécifiquement pour une brute, non orienté, graphe, qui est ce qu'il semble que vous êtes en train de faire, je suggère de faire un BFS.

    Quoi? Dijkstra n'est pas toutes les paires.

    OriginalL'auteur adelbertc

  2. 4

    Après avoir trouvé le chemin le plus court à partir de la SOURCE unique, nous avons besoin de commencer à DESTINATION de backtrack son prédécesseur, afin d'imprimer le chemin.

    Print-Path(G,s,v)
{
    if(v==s)
        print s;
    else if (pi[v]==NULL)       
        print "no path from "+s+" to "+v;
    else{
        Print-Path(G,s,pi[v])
        print v;
    }
}

    codes au-dessus de courtoisie à l'Introduction de l'Algorithme, MIT press

    OriginalL'auteur Daniel

  3. 2

    La meilleure façon d'aborder cette question consiste à penser en termes de chemins accessible à partir de chaque nœud retour à la source, communément désigné par v. en tant Que mise à jour de chaque nœud donné que la distance de garder une trace de son successeur direct sur ce chemin de v. ce nœud est le nœud parent dans la plus courte distance-à-v de l'arbre. Lorsque vous avez construit que de la carte mère, pour trouver le plus court chemin de v à w construire le chemin d'accès dans l'ordre inverse: w, parent[w], parent[parent[w]], ...

    OriginalL'auteur Tom Payne