im trying to get my code to perform dijkstra's algorithm on my adjacny matrix, it works great for the inital row (0) but i cant get it working for any other value?!

void dijkstra (int a[size][size], int matSize, string CityID[size])
{
    string startCity;
    cout << "Enter start city : ";   
    cin >> startCity;
    
    int MAX = matSize;
    int startCityID = getCityID(startCity, CityID, MAX); //gets the value of the city
   
    //Declaring a priority queue of edge - stipulating greater so it orders on a 
    //min-heap i.e. pq.top() will be smallest weight edge in pq.
    priority_queue <edge, vector<edge>, greater<edge> >pq;

  
    insertInfinity(a,matSize); //replaces all zeroes with 9999
    
    // set to source
    int* parent = NULL;
    parent = new int[MAX];

    for (int fillP = 0; fillP <= MAX; fillP++)
    {
         parent[fillP] = false;  
    }
    
    //Creates a dynamic array to store the vertex sets, and sets the default
    //boolean operator to false.
    bool* inVertexSet = NULL;
    inVertexSet = new bool[MAX];

    for (int fillVS = 0; fillVS <= MAX; fillVS++)
    {
         inVertexSet[fillVS] = false;  
    }
   
    //
    int* weights = NULL;
    weights = new int[MAX];
    
    int store;
    
    for (int fillW = 0; fillW <= MAX; fillW++)
    {
         store = a[startCityID][fillW];
         weights[fillW] = store;
    }
    
    for (int col  = 0; col < MAX ; col++)
    {
         if (a[startCityID][col] < B) // B = 9999
         {
              pq.push (edge( a[startCityID][col],col,0));  // edges adjacent to source
         }
    }
  
    inVertexSet[startCityID] = true;  // set source to be in vertex set
  
    while (!pq.empty())
    {
         edge p = pq.top(); // get edge with smallest weight
         int dist = p.weight;
         int v = p.vertex1;  // note that vertex2 is already in vertexset
         pq.pop();
         
         if (!inVertexSet[v])
         { 
              inVertexSet[v] = true; // know least cost path to v
         
              for (int u=startCityID; u < MAX; u++)
              {
                   if (!inVertexSet[u])
                   {
                        if (weights[u] > weights[v]+a[v][u])
                        {
                             weights[u] = weights[v] + a[v][u];
                             // keep track of path here by recording u's parent as v
                             parent[u] = v;
                             pq.push(edge(weights[u],u,v));
                        }
                   }
              }
         }
    }
    
    
    
  for (int i=0;i<MAX;i++)
  {
     cout << "\nDISTANCE to "<<  CityID[i] << " = " << weights[i] << endl;
     cout << "PATH from " << startCity << " to vertex " << CityID[i] << endl;
     printpath(i,parent, CityID);
     cout << endl;
  }  system("pause");

}

Edited 6 Years Ago by timb89: n/a

Give any sample data to test it? And what output you get when you enter your sample data? Debugging other's code is not easy; besides, I have already forgotten about the algorithm... Need to read about it again...

Give any sample data to test it? And what output you get when you enter your sample data? Debugging other's code is not easy; besides, I have already forgotten about the algorithm... Need to read about it again...

well i had it working for the first initial row and column. so i developed a function to swap the chosen row and column with the initial one. but still no luck?

timb:

When you post something and ask for help, you need to be clear and give as much information as you can because those who are willing to help you would be able to understand your problem without going through your whole CODE. It is not easy to look at a problem which consists of only code.

You have already compiled your code and you knew what input and output look like, but I don't. If you give what the input would be and what the real output is, it would be easier to debug your code without going through your code or try to compile it; besides, I wouldn't be able to compile your code in a local machine anyway. You have other data type that I don't have or know how it is implemented (priority_queue). Even though, I could go through all the troubles to implement it, I still don't know whether it is the same as what you are using.

Anyway, did you follow the algorithm line by line? To me, it looks a bit different. Not sure why you think that once you assigned a value to inVertexSet[x], the value is the shortest distance. In the algorithm, you still need to check whether there is an alternative route which gives a shorter distance every time a node is visited. You may need to take another look at the algorithm on wikipedia. Also, this would assume that you have correctly created the priority queue.

Oh and by the way, why do you use top() and then pop()? You could just use pop() right away because it should return an edge for you and at the same time remove the edge from the queue. The top() function is used to get the first edge in the queue without modifying it, but your purpose is to get the edge and modify the queue regardless.

Edited 6 Years Ago by Taywin: n/a

This article has been dead for over six months. Start a new discussion instead.