Почему эта реализация Dijkstra (graph) не работает? - PullRequest
Новая
       5

Почему эта реализация Dijkstra (graph) не работает?

2 голосов
/ 03 февраля 2010

Я сделал эту реализацию для этой проблемы: 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();
}

Я не знаю, почему мой код не генерирует правильный ответ для тестовых случаев. Если кто-то может помочь мне улучшить код, сделайте это: D

Ответы [ 3 ]

4 голосов
/ 04 февраля 2010

Прежде всего, неверный код разбора графа.Первая строка определяет ширину и высоту, где ширина - количество символов в строке, высота - количество строк.Поэтому поменяйте местами &a и &b в первом scanf или поменяйте местами порядок вложенных циклов for (но не обоих).Кроме того, мне пришлось добавить фиктивные вызовы scanf("%c", &dummy); в разных местах, чтобы отфильтровать новые строки.Простой дамп, такой как этот, поможет определить, была ли ваша карта проанализирована правильно: 

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

Примечание: я также установил map[i][j] в 0 для 'S' и 'D', также изменяя повторяющиесяif операторов в цепочку if; else if; else.Это делает алгоритм более устойчивым, поскольку вы можете в общем случае добавлять время из источника или получателя.

Теперь перейдем к самому алгоритму ....

Каждый цикл алгоритма увеличивается result по текущему весу местоположения карты.Однако алгоритм ищет несколько путей одновременно (т.е. количество записей в очереди с приоритетами), и поэтому result заканчивается суммой весов всех обработанных узлов, а не веса текущего пути.Текущий вес пути равен top.temp, поэтому вы можете исключить переменную result и просто вернуть top.temp при достижении пункта назначения.

Также, как отмечалось в других ответах, вам нужно использовать X[i] и Y[i] в вашем внутреннем цикле, иначе вы ищете только в одном направлении.

Теперь, из-за сложения / вычитания из X[i] и Y[i], вы, скорее всего, получите доступ к map[][] outдиапазона (-1 или 25).Поэтому я рекомендую переместить ограждения if во внутреннюю петлю for для защиты от доступа вне зоны действия.Это также позволяет избежать заполнения очереди приоритетов недопустимыми возможностями.

Вот моя версия алгоритма с минимальными исправлениями для справки: 

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;

Надеюсь, это поможет.

2 голосов
/ 03 февраля 2010

Почему у вас 0 индексов? 

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

Разве это не более читабельно: 

bool operator <(const node &s,const node &r)
{
    return (s.time>r.time);
}
2 голосов
/ 03 февраля 2010

Вы используете X[0] и Y[0] вместо X[i] и Y[i] в этом внутреннем цикле.

Кстати, кроме этого, ваша Дейкстра очень неэффективна. Во-первых, вы помещаете узлы в очередь, даже если они уже были посещены, а во-вторых, у вас может быть несколько одинаковых узлов в очереди, только с разным временем. В конечном итоге ни одна из этих вещей не влияет на результат, но вы меняете сложность.

Редактировать: О, tempa.time должно равняться top.time плюс вес ребра, а не только вес ребра.

...