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?