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

[Вероника99]

Здравствуйте. Прочитав следующую статью возник вопрос по поводу определения кратчайших путей.http://hci.fenster.name/304y/lab5/
Там сказано,чтобы для того чтобы найти вершины,через которые лежит кратчайший путь, нужно присвоить некое значение специальной матрице С и т.д. Сделала все как там сказано, вот часть кода. Выводит совсем не то,что нужно. Саму логику нахождения именно путей графа не очень понимаю. Буду очень благодарна,если объясните как можно реализовать путь по вершинам

for (i=0; i<V; i++) 
        D[i][i]=0; //диагональ
    for (k=0; k<V; k++)
    for (i=0; i<V; i++)
    {
        C[k][i]=k;
    for (j=0; j<V; j++)
    if (D[i][k] && D[k][j] && i!=j)         
    if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
        {
            D[i][j]=D[i][k]+D[k][j];
             C[i][j] = C[k][j];
            cout<<" D[i][j] "<<D[i][j]<<endl;
             cout<<" C[i][j] "<<C[i][j]<<endl;
        }
    }

[Utkin]

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

[Poma][a]

.То есть сначала между двумя, потом между тремя (с учетом уже вычисленного расстояния между двумя предыдущими и т.д.).

Да разве?
Потом это расстояние может быть улучшено, не?

[Utkin]

Да разве?
Потом это расстояние может быть улучшено, не?

Честно не помню .

[FPaul]

Пояснения есть, например, на e-maxx.ru, здесь и здесь. Также можно задать поиск в интернет по фразе "Floyd-Warshall".
Мне трудно ориентироваться в программе на С++, но ощущение, что инициализация матрицы C должна происходить до начала поиска, а не в самом внутреннем его цикле, также вывод результатов - по окончании работы, и ещё непонятны оба условия в обоих if - таких и близко нет в описаниях.

[Вероника99]

Сделала отдельный цикл инициализации матрицы С перед началом выполнения алгоритма

for (k=0; k<V; k++)
	for (i=0; i<V; i++)
		C[k][i]=k;

При выводе значений матрицы С в главном цикле,выдает совсем не те значения. Мне нужно,чтобы после ввода двух вершин,программа выводила самый короткий путь между ними.В той статье написано,что нужно иметь двумерный массив,в который заносятся все значения подряд,не отделяя путь между одной парой вершин,от другой. Как сделать так,чтобы при вводе двух вершин,выдавало путь между ними?Саму длину между вершинами программа считает правильно,а вот как сохранить путь по вершинам,я не понимаю

[Poma][a]

Дык все просто
Сначала задаем матрицу смежности :

for (int i = 0; i < n; i++)
   for (int j = 0; j < n; j++) 
        cin >> v[i][j];

Вот
Прекрасно
Давайте теперь бахнем Флойда
<тут код>

Потом делаем такую вот красоту

cin >> m; // количество запросов
for (int i = 0; i < m; i++)
{
    int a, b;
    cin >> a >> b;
    cout << v[a-1][b-1] << endl;
    
}

Вот и все

[Вероника99]

Poma][a,спасибо за ответ.
Я внутри главного цикла сделала следующее

{
			D[i][j]=D[i][k]+D[k][j];
			 C[i][j] = C[k][j];
			cout<<"\n D[i][j] "<<D[i][j]<<endl;
	
			cout<<"  "<<i+1<<"  "<<C[i][j]<<" "<<j+1<<endl;
		}

Оно выводит начальную вершину,последнюю вершину и между ними предпоследнюю вершину в пути. А что делать в том случае,если в проходе вершин больше чем 3,т.е перед C[i][j] есть еще две вершины например?

[FPaul]

Цитирую e-maxx

Восстановление самих путей
Легко поддерживать дополнительную информацию — так называемых "предков", по которым можно будет восстанавливать сам кратчайший путь между любыми двумя заданными вершинами в виде последовательности вершин.
Для этого достаточно кроме матрицы расстояний d[][] поддерживать также матрицу предков p[][], которая для каждой пары вершин будет содержать номер фазы, на которой было получено кратчайшее расстояние между ними. Понятно, что этот номер фазы является не чем иным, как "средней" вершиной искомого кратчайшего пути, и теперь нам просто надо найти кратчайший путь между вершинами i и p[i][j], а также между p[i][j] и j. Отсюда получается простой рекурсивный алгоритм восстановления кратчайшего пути.

Я так понимаю, что правильно считает D[][]. Судя по e-maxx матрица C[][] и есть вспомогательная структура, позволяющая "восстановить" путь.
Кажется, что задача поиска пути между i и j сводится к
1. Пусть нашу рекурсивную проседуру вызывают так RestorePath(i, j). Дальше идёт оаисание самой подпрограммы.
2. Зная i и j получаем k:=p[i][j].
3.1. Если между i и k путь короткий, то печатаем его.
3.2. Иначе вызываем рекурсивно подпрограмму RestorePath(i, k)
4.1. Если между k и j путь короткий, то печатаем его.
4.2. Иначе вызываем рекурсивно подпрограмму RestorePath(k, j)

Короткий путь - наличие дуги между i и k по матрице смежности.

Наверное так.

[Poma][a]

Не понял..
Вы хотите вывести весь путь?
Мол путь из вершины A в вершину B проходит через вершины c1, c2, .., ck?