Why this Dijkstra (graph) implementation isn't working ??

Question

I made this implementation for this problem : http://www.spoj.pl/problems/SHOP/

---

#include<iostream>
#include<stdio.h>
#include<queue>
#include<conio.h>
#include<string.h>
using namespace std;

struct node
{
    int x;
    int y;
    int time;
};
bool operator <(const node &s,const node &r)
{
    if(s.time>r.time)
    return true;
    else return false;
}
node beg,src,dest,tempa;
int b,a,temp;
int map[25][25];
bool vis[25][25];
int X[]={1,0,-1,0};
int Y[]={0,1,0,-1};


int djs_bfs(node src,node dest)
{
    int result=0;
    priority_queue<node>pq;
    pq.push(src);
    while(!pq.empty())
    {
        node top = pq.top();
        pq.pop();
        if(top.x==dest.x && top.y==dest.y) return result;
        if(top.x<0 || top.x>=a) continue;
        if(top.y<0 || top.y>=b) continue;
        if(vis[top.x][top.y]) continue;

        vis[top.x][top.y]=true;
        result+=map[top.x][top.y];
        for(int i=0;i<4;i++)
        {
            tempa.x=top.x+X[0];
            tempa.y=top.y+Y[0];
            tempa.time=map[top.x+X[0]][top.y+Y[0]];
            pq.push(tempa);
        }
    }
    return -1;
}

int main()
{
    memset(vis,false,sizeof(vis));
    scanf("%d %d",&a,&b);
    while(a != 0)
    {
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
            {
                scanf("%c",&temp);
                if(temp=='X') {map[i][j]=0;vis[i][j]=true;}
                if(temp=='S') {src.x=i;src.y=j;src.time=0;}
                if(temp=='D') {dest.x=i;dest.y=j;dest.time=0;}
                else map[i][j]=temp-'0';
            }
        cout<<djs_bfs(src,dest)<<endl;
        scanf("%d %d",&a,&b);
    }
    return 0;
    getch();
}

I don't know why my code doesn't generate the right answer for the testcases. If someone can help me improve the code, please do so :D

Answer 1

You're using X[0] and Y[0] instead of X[i] and Y[i] in that inner loop.

By the way, other than that your Dijkstra's is very inefficient. First, you're pushing nodes onto the queue even when they have already been visited, and secondly, you may have several of the same node in the queue, just with different times. Ultimately neither of these things effect the outcome, but you're changing the complexity.

Edit: Oh, tempa.time should equal top.time plus the edge weight, not just the edge weight.

Answer 2

Why do you have 0 indexes?

tempa.x=top.x+X[0];
tempa.y=top.y+Y[0];
tempa.time=map[top.x+X[0]][top.y+Y[0]];

Nitpick:

bool operator <(const node &s,const node &r)
{
    if(s.time>r.time)
    return true;
    else return false;
}

Isn't this more readable:

bool operator <(const node &s,const node &r)
{
    return (s.time>r.time);
}

Answer 3

First of all, the graph parsing code is incorrect. The first line specifies width and height, where the width is the number of characters per line the height is the number of lines. Therefore, swap &a and &b in the first scanf, or swap the order of the nested for loops (but not both). Also, I had to add dummy scanf("%c", &dummy); calls at various places to filter out newlines. A simple dump, such as this, will help determine if your map was parsed correctly:

cout << "a=" << a << endl;
cout << "b=" << b << endl;
for (int i=0; i<a; i++) {
    for(int j=0; j<b; j++) {
        cout << (char)('0' + map[i][j]) << ",";
    }
    cout << endl;
}

Note: I also set map[i][j] to 0 for 'S' and 'D', also changing the repeated if statements into an if; else if; else chain. This makes the algorithm more robust, since you can generically add time from the source or destination.

Now, on to the algorithm itself....

Each loop of the algorithm increments result by the current map location weight. However, the algorithm is searching multiple paths simultaneously (i.e., the number of entries in the priority queue), and therefore result ends up being the sum of all processed node weights, not the current path weight. The current path weight is top.temp, and therefore you can eliminate the result variable and simply return top.temp when you reach the destination.

Also, as other answers noted, you need to use X[i] and Y[i] in your inner loop, otherwise you are only searching in one direction.

Now, because of the addition/subtraction from X[i] and Y[i], you will likely access map[][] out of range (-1 or 25). Therefore, I recommend moving the if guards to the inner for loop to guard against the out-of-range access. This also avoids filling the priority queue with illegal possibilities.

Here is my version of the algorithm, with minimal corrections, for reference:

priority_queue<node>pq;
pq.push(src);
while(!pq.empty())
{
    node top = pq.top();
    pq.pop();

    if(top.x==dest.x && top.y==dest.y) return top.time;
    if(vis[top.x][top.y]) continue;

    vis[top.x][top.y]=true;

    for(int i=0;i<4;i++)
    {
        tempa.x=top.x+X[i];
        tempa.y=top.y+Y[i];
        if(tempa.x<0 || tempa.x>=a) continue;
        if(tempa.y<0 || tempa.y>=b) continue;
        tempa.time=top.time + map[tempa.x][tempa.y];
        pq.push(tempa);
    }
}
return -1;

I hope this helps.