Проход по вершинам графа

[Вероника99]

Poma][a,кстати в вашем варианте с векторами, у меня тоже функция поиска пути не выдает никакого результата

[FPaul]

Вероника99,
В общем поставил я себе на комп gcc. С нуля набрал прогу (портировал свой паскаль-исходник). Работает.
Причины:
1. Если в описании алгоритма написано о INFINITY - надо использовать.
2. Я плохо знаком с С и неправильно реализовывал цикл while.

Недостатки в моём исходнике
1. Я не умею работать с указателями в С и поэтому не могу разделить функции FU и печать пути - надо передавать массивы по ссылке и вызывать печать из main.
2. Всегда нужно разделять расчёты и вывод на экран. Из-за п.1 у меня не получилось.
3. Я не знаю как определить число MAXINT, поэтому применил INFINITY=10000.

#include <iostream>

using namespace std;

#define INFINITY 10000

//алгоритм Флойда-Уоршелла
int FU(int mV[][5], int D[][5], int C[][5], int V,int a,int b)
{
    /*
    матрицу веса дуги mV преобразуем в требуемый для алгоритма вид D
    - если i=j, то D[i, j]:=0
    - если из i в j нет ребра, то D[i, j]:=INFINITY (бесконечности)
    - иначе D[i, j] равно весу ребра из i в j
    подготовим матрицу для восстановления пути C
    */
    D=mV;
    for(int i=0; i<V; i++)
    {
        for(int j=0; j<V; j++)
        {
            if (D[i][j]==0)
                D[i][j]=INFINITY;
            if(i==j)
                D[i][j]=0;
            C[i][j]=i;
        }
    }
    /*
    Непосредственно сам цикл алгоритма Флойда-Уоршелла
    */
    for(int k=0; k<V; k++)
    {
        for(int i=0; i<V; i++)
        {
            for(int j=0; j<V; j++)
            {
                if( (D[i][k]!=INFINITY) && (D[k][j]!=INFINITY) )
                {
                    if(D[i][j]>D[i][k]+D[k][j])
                    {
                        D[i][j]=D[i][k]+D[k][j];
                        C[i][j]=C[k][j];
                    }
                }
            }
        }
    }

    cout << " D[][]:"<<endl;
    for(int i=0; i<V; i++)
    {
        for(int j=0; j<V; j++)
        {
            if(D[i][j]!=INFINITY)
                cout << " " << D[i][j];
            else
                cout << " inf";
        }
        cout <<endl;
    }

    cout << " C[][]:"<<endl;
    for(int i=0; i<V; i++)
    {
        for(int j=0; j<V; j++)
        {
            cout << " " << C[i][j];
        }
        cout <<endl;
    }

    // вывод пути между a и b
    if(a==b)
    {
        cout << "A==B" << endl;
        return 0;
    }
    if(D[a][b]==INFINITY)
    {
        cout << "No path" << endl;
        return 0;
    }
    // запись пути в стек
    int stk[1000];
    int len;
    int k;
    k=b;
    stk[0]=k;
    len=1;
    do
    {
        k=C[a][k];
        stk[len++]=k;
    }
    while(k!=a);
    // извлечение из стека и печать пути
    cout << "Path: <";
    for (int i=len; i>0; i--)
    {
        cout << " " << stk[i-1];
    }
    cout << ">" << endl;
}

int main()
{
    int GR[5][5]=
    {
        {0,3,2,0,0},
        {0,0,0,4,0},
        {0,0,0,6,0},
        {0,0,0,0,2},
        {0,0,0,0,0}
    };
    int D[5][5], C[5][5];
    FU(GR, D, C, 5, 3, 1);
    int GR2[5][5]=
    {
        {0,0,5,0,0},
        {7,0,0,0,10},
        {0,7,0,0,0},
        {0,0,6,0,4},
        {0,0,1,0,0}
    };
    FU(GR2, D, C, 5, 3, 1);
    return 0;
}

Результат работы проги

 D[][]:
 0 3 2 7 9
 inf 0 inf 4 6
 inf inf 0 6 8
 inf inf inf 0 2
 inf inf inf inf 0
 C[][]:
 0 0 0 1 3
 1 1 1 1 3
 2 2 2 2 3
 3 3 3 3 3
 4 4 4 4 4
No path
 D[][]:
 0 12 5 inf 22
 7 0 11 inf 10
 14 7 0 inf 17
 19 12 5 0 4
 15 8 1 inf 0
 C[][]:
 0 2 0 0 1
 1 1 4 1 1
 1 2 2 2 1
 1 2 4 3 3
 1 2 4 4 4
Path: < 3 4 2 1>

Посмотри и сравни со своей реализацией.

[Вероника99]

FPaul,спасибо огромное. Программа работает,но единственное что, все там же проблема,не показывает предыдущие вершины в путях,в матрице выводится только предпоследняя вершина...

[FPaul]

Я не пойму о чём речь. Приведи пример таких данных вместе с эталонным ответом.

[Poma][a]

Утро доброе, граждане полуночники

Poma][a, а что ты изменил?

Отформатировал, не? Значит студия наврала..

Там все матрицы что-то делают.

Эт понятно

Если это не хранить, то для каждой новой пары вершин опять надо всё пересчитывать O(n^3).

Не-не-не
У нас же есть матрица смежности и матрица путей
За квадрат точно смогем восстановить

[FPaul]

Утро доброе!!!
А я, кажется, стелепатировал , что у ТС не получается!!!

Сообщение от Вероника99

Если я ввожу например 1 5, программа глючит. Если две соединяющиеся вершины,выводит два раза вторую вершину.

Ха, а матрица с индексами от 0 до 4, и вершины нумеруются от 0 до 4. Вставь в начале вывода путей проверку на корректные диапазоны a и b.

[Вероника99]

FPaul, а нет,все работает,да,это я затупила,надо при вводе а ,b делать проверку, я у себя матрицу нарисовала начиная с 1 и до 5. Спасибо огромное!!

[Вероника99]

А как можно найти самый длинный путь между двумя вершинами?Пробовала создать еще один массив, проделать все тоже самое что и с массивом С,только сделать отдельное условие if с противоположным знаком,в итоге выводит только начальную и последнюю вершину

[Poma][a]

Ну дык.. Тоже самое, но поменять условие в развилке
Если снова вывод пути, то и там махнуть чуть-чуть..

А можно выпендриться и проверить есть ли у нас цикл положительного веса.. Если такой имеется, то решения (для части вершин) не будет

[Вероника99]

А что нужно поменять в этой программе для того,чтобы граф был представлен списком смежности? Если я ввожу список таким образом,как сделать так чтобы двумерный массив заполнился значениями из одномерного массива terminal. Часть программы взята с сайта http://kvodo.ru/adjacency-list.html

void Add(int v, int u) //добавление ребра
{
k=k+1;
terminal[k]=u;
next_el[k]=head[v];
head[v]=k;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
k=0;

cout<<"Вводите смежные вершины:"<<endl;
for (i=0; i<m; i++)
{
cin>>v>>u;
Add(v, u);

cout<<endl;
}