Dijkstra's algorithm for finding the shortest path?

2
votes

So I have been trying to implement the Dijkstra Algorithm to find the shortest path within a graph, but am running into several errors as I go along. First off, here's the actual question and the components I was given with it.

"Write a c++ function to implement Dijkstra's algorithm on a graph. The graph implementation is on Moodle, called IntroToGraphs.zip.The function takes two parameters: starting vertex and destination vertex. Print the shortest path and the shortest distance from the starting vertex to the destination vertex."

void Graph::Dijkstra(string starting, string destination);

The vertex structure has been changed to include "visited", "distance" and "previous".

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

Here is the definition of the Graph class:

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;

};

Here's the code I've written:

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

The error I'm hitting with this code is that minDistance is an unidentified variable at the very bottom, when I set tmp->distance to it. Any clues about what I need to fix?

3
c++algorithmdijkstra

3 Answers

3
votes

Anything declared in the loop is scoped to that loop and cannot be accessed outside the curly braces. In fact, you don't even need a loop to create a new scope. More Info

The variable minDistance in declared inside the while loop.

1
votes

You need to initialize minDistance outside the scope of the while loop.

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

The value of minDistance can be changed inside of the loop.

1
votes

solved also never seems to be populated. You have :

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

those are all the cases where i can find "solved" and no values are ever put in it so the for loop should never run because solved.size() is always equal to 0