Ändern der Dijkstra-Algorithmus, um den Kürzesten Pfad Zwischen Zwei Knoten

So, ich habe gesehen, ähnliche Fragen dazu, aber nicht ganz genau, was ich Suche. Ich brauche zum ändern der Dijkstra-Algorithmus zur Rückkehr der kürzeste Weg zwischen einem Scheitelpunkt S (source) und ein Knoten X (Ziel). Ich glaube, ich habe herausgefunden, was zu tun ist, aber ich möchte etwas helfen. Hier ist der pseudocode habe ich geändert.

 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];

Den code stammt von Wikipedia und modifiziert werden: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Schaut das richtig?

  • Warum würden Sie brauchen, um es zu ändern? Das ist genau das, was es tut. Wenn man alle kantengewichte auf 1.
  • Dies ist der code, den ich bereits geändert. Also wenn es funktioniert dann Super.
  • Auch, wie der vertex-Auswahl in Dijkstra ist greedy, sobald du "u = destination", können Sie brechen die Schleife ab.
  • das macht sehr viel Sinn. Danke.
InformationsquelleAutor csnate | 2012-11-19
  1. 4

    Dijkstra-Algorithmus muss nicht geändert werden, es ist ein all-pairs-shortest-path-Algorithmus. Es scheint, wie Sie versuchen, zu finden den kürzesten Weg zwischen zwei bestimmten Knoten - Dijkstra übernimmt dies in Ordnung.

    Wenn Sie wollen etwas, das speziell für eine ungewichtete, ungerichtete Graphen, was ist, was es scheint, wie Sie tun, ich würde vorschlagen, tun eine BFS.

    • Was? Dijkstra ist nicht alle Paare.
    InformationsquelleAutor adelbertc
  2. 4

    Nach der Suche nach dem kürzesten Pfad ausgehend von der einzigen QUELLE, wir müssen beginnen, mit dem ZIEL zur Umkehr zu seinem Vorgänger, um zu drucken den Weg.

    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 oben, mit freundlicher Genehmigung zur Einführung in den Algorithmus, MIT press

    InformationsquelleAutor Daniel
  3. 2

    Der beste Weg, dies zu nähern, ist zu denken in Bezug auf die Pfade von jedem erreichbaren Knoten zurück zur Quelle, allgemein bezeichnet durch v. Wie Sie aktualisieren jedes Knotens ist die Distanz, verfolgen seine direkten Nachfolger auf den Weg zu v., Die node ist der node, ist die Muttergesellschaft der in der kürzesten Distanz zu v-Baum. Wenn Sie gebaut haben, dass die übergeordneten map, finden Sie den kürzesten Weg von v zu w bauen Sie den Pfad, in umgekehrter Reihenfolge: w, parent[w], parent[Elternteil[w]], ...

    InformationsquelleAutor Tom Payne
Schreibe einen Kommentar