Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Самый короткий путь в ориентировонном графе

Автор: sas8899 25.12.2007, 20:03

Нужно найти самый короткий путь между двумя вершинами ориентированного графа.
Знаю то нужно пройти граф через Breadth First Search, но не знаю как посчитать этот путь.

Код



int pathXY(struct graf d,int x,int y)
{
    int i,j,is,iss;
    int s[100],viz[100];//в массив S записываю вершины при прохождении графа BFS, а в VIZ запоминает если эту вершину посетил
    if (x==y) return 0;
    for (i=0;i<d.n;i++) //задаю начальные значения в массивах
    {
        s[i]=-1;
        viz[i]=-1;
    }
    is=0;
    s[is]=x;
    viz[x]=0;
    iss=0;
    while (s[iss]!=y && s[iss]!=-1)//прохожу BFS и пишу вершины в массив S
    {
        for (j=0;j<d.n;j++)
        {
            if (d.a[s[iss]][j] && viz[j]==-1)
            {
                is++;
                s[is]=j;
                viz[j]=viz[s[iss]]+1;
            }
        }
        iss++;
    }
    return viz[y];
}

Заранее благодарю за помощь.

Автор: maxim1000 26.12.2007, 16:56

на данный момент для каждой вершины viz хранит одно из двух значений:
0 - не посещалась
1 - посещалась
можно расширить
-1 - не посещалась
L>=0 - посещалась и кратчайшее расстояние = L
т.е. вместо viz[j]=1 можно писать viz[j]=viz[s[iss]]+1

P.S.
всё-таки я бы советовал более красноречиво называть переменные smile

P.P.S.
на всякий случай уточню: все рёбра имеют одинаковую длину?

Автор: sas8899 26.12.2007, 18:35

maxim1000, да все ребра имеют одинаковую длину.

P.S Что имеешь ввиду насчет переменных? Как правильно их называть?

P.P.S. Отредактировал код, это ты имел ввиду?

Автор: maxim1000 26.12.2007, 19:02

ну хотя бы x -> start, y -> finish

Автор: sas8899 26.12.2007, 19:05

вот с этого файла у меня создается граф

7
0 1 0 0 0 0 0
1 0 1 0 0 0 0
1 0 0 1 0 0 0
0 0 1 0 1 0 0
1 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

когда существует путь от вершины Х к вершине У то все считает нормально, а вот к примеру есть путь от 4 до 5, но обратно нету, и если ввожу х=5 и у=4 то выдает ответ 4, хотя никак из 5 в 4 не попасть.

Добавлено через 1 минуту и 3 секунды
maxim1000, хорошо smile

буду иметь ввиду на будующее, спасибо smile

Автор: maxim1000 26.12.2007, 19:11

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

Добавлено через 3 минуты и 37 секунд

Цитата(sas8899 @ 26.12.2007, 19:05

)

хотя никак из 5 в 4 не попасть.

это зависит от того, как задаётся матрица
если "откуда" откладывается по горизонтали, а "куда" - по вертикали, то из 5 в 4 как раз можно попасть

Добавлено через 3 минуты и 52 секунды
т.е. стоит ещё и проверить, правильно ли читается матрица...

Автор: sas8899 26.12.2007, 20:21

Код



void create(struct graf* d)
{
    FILE *filein;
    int i,j;

    filein=fopen("pr1.in","r");
    fscanf(filein,"%d\n",&d->n);
    for (i=0; i<d->n; i++)
    {
        for (j=0; j<d->n; j++)
            fscanf(filein,"%d",&d->a[i][j]);
        fscanf(filein,"\n");
    }
}

Вот как у меня читается матрица.

P.S. Отсчет вершин начинается с 0.

Добавлено через 11 минут и 57 секунд
maxim1000, все спасибо я разобрался в чем дело.

P.S. Исправил код, если кому-то еще понадобится.