2016-04-08 25 views
2

Also habe ich versucht, den Dijkstra-Algorithmus zu implementieren, um den kürzesten Pfad innerhalb eines Graphen zu finden, aber ich stoße auf mehrere Fehler, wenn ich weitergehe. Zunächst einmal, hier ist die eigentliche Frage und die Komponenten, die ich damit bekommen habe. .Dijkstra-Algorithmus für die Suche nach dem kürzesten Weg?

„eine C++ schreiben Funktion Dijkstra-Algorithmus auf einem Graphen implementieren Der Graph-Implementierung ist auf Moodle, genannt IntroToGraphs.zip.The Funktion nimmt zwei Parameter:. Startecke und Ziel Vertex drucken den kürzesten Weg und die kürzeste Entfernung von der Startknoten zum Zielknoten. "

void Graph :: Dijkstra (String beginnt, String-Destination);

Die Vertexstruktur wurde so geändert, dass sie "besucht", "Entfernung" und "vorherige" enthält. Hier

struct adjVertex{ 
    vertex *v; 
    int weight; 
}; 
struct vertex{ 
    std::string name; 
    bool visited; 
    int distance; 
    vertex *previous; 
    std::vector<adjVertex> adj; 
}; 

ist die Definition der Graph Klasse:

class Graph 
{ 
    public: 
     Graph(); 
     ~Graph(); 
     void addEdge(std::string v1, std::string v2, int weight); 
     void addVertex(std::string name); 
     void displayEdges(); 
    void Dijkstra(string sourceVertex, string destinationVertex); 
    protected: 
    private: 
     std::vector<vertex> vertices; 

}; 

Hier ist der Code, den ich geschrieben habe:

void Graph::Dijkstra(string starting, string destination){ 
vertex * start; 
vertex * ending; 
for(int i=0;i<vertices.size();i++){ 
    vertices[i].visited=false; 
    vertices[i].distance=INT_MAX; 
    vertices[i].previous=NULL; 
    if(vertices[i].name==starting){ 
     start=&vertices[i]; 
    } 
    if(vertices[i].name==destination){ 
     ending=&vertices[i]; 
    } 
} 
start->visited=true; 
start->distance=0; 
vector<vertex *> solved; 
vector<vertex *> path; 
vertex *tmp; 
vertex *parent; 
while(!ending->visited){ //pseudo territory 
    int minDistance=INT_MAX; 
    tmp=NULL; 
    for(int i=0;i<solved.size();i++){ 
     vertex * s=solved[i]; 
     for(int y=0;y<s->adj.size();y++){ 
      if(!s->adj[y].v->visited){ 
       s->distance=s->distance+s->adj[y].v->distance; 
       if(s->distance<minDistance){ 
        tmp=s->adj[y].v; 
        minDistance=s->distance; 
        parent=s->previous; 
       } 
      } 
     } 
    } 
} 
tmp->distance=minDistance; 
tmp->previous=parent; 
tmp->visited=true;} 

Der Fehler, den ich mit diesem Code bin schlagen ist, dass MinDistance ist eine nicht identifizierte Variable ganz unten, wenn ich tmp-> Abstand darauf setze. Irgendwelche Hinweise darauf, was ich reparieren muss?

Antwort

3

Alles, was in der Schleife deklariert wird, ist auf diese Schleife beschränkt und kann nicht außerhalb der geschweiften Klammern erreicht werden. In der Tat brauchen Sie nicht einmal eine Schleife, um einen neuen Bereich zu erstellen. More Info

Die Variable minDistance wird in der while-Schleife deklariert.

1

Sie müssen minDistance außerhalb des Bereichs der while-Schleife initialisieren.

int minDistance=INT_MAX; 
while(!ending->visited){ 
    ... 
    minDistance=someOtherValue 
    ... 
} 
tmp->distance=minDistance; 

Der Wert von minDistance kann innerhalb der Schleife geändert werden.

1

gelöst scheint auch nie ausgefüllt werden. Sie haben:

vector<vertex *> solved; 
... 
    for(int i=0;i<solved.size();i++){ 
     vertex * s=solved[i]; 

diejenigen sind alle Fälle, in denen i „gelöst“ finden können und keine Werte je auf ihr so ​​die for-Schleife setzen sollte niemals ausgeführt werden, da solved.size() auf 0

immer gleich ist
Verwandte Themen