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

Question

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

Answer 1

Прежде всего, код анализа графика неверный. Первая строка определяет ширину и высоту, где ширина - это количество символов в строке высота - количество линий. Поэтому своп &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[][] вне диапазона (-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;

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

Answer 2

Почему у вас 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);
}

Answer 3

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

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

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