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

[FPaul]

Смотри. Ты не можешь понять где ошибка - на стадии расчёта D, на стадии расчёта C или при определении пути между a и b.
Поэтому предлагаю отладить твою программу по какому-нибудь эталону. Я пару часов назад отлаживал по примеру отсюда. В начальных условиях задал матрицу весов рёбер GR, а на выходе получил матрицу расстояний D. Потом прямо из программы дал задание найти пути для двух-трёх пар вершин и проверил по изображению, что это так.
После вычисления матриц я их распечатал для сравнения.
Предлагаю и тебе после вычисления D и C вывести их на экран и сравнить с эталоном.
Ещё, проглядывая твой код увидел, что перед RestorePath присутствуют глобальные переменные y и C[][] - убери их или перенеси в соответствующее место. Также, несмотря на уверения Poma][a, заключи все условия в скобки (Pascal даже отказывается компилить такое).
И чтобы было проще, приведи свой код в виде аттача (из расширенной формы).

[Вероника99]

С расчетом D все в порядке 100%, оно все правильно считает,проблемы с матрицей С,которая должна выводить путь между двумя введенными вершинами. Проблемы имеются с рекурсивной функцией,я вообще не понимаю,что там происходит,ну или на других статьях советуют еще циклично,а не рекурсивно(

[Poma][a]

Также, несмотря на уверения Poma][a, заключи все условия в скобки (Pascal даже отказывается компилить такое).

Ей Богу так тыц

[FPaul]

Вероника99, Приаттач исходник.
Покажи, что получается - у меня нет C.
Если не можешь скопировать консоль, сделай перенаправление в текстовый файл или из проги или при запуске из командной строки.

Poma][a, меня учили, что приоритет изменяется от компилятора к компилятору (vc, gcc, icc) и не стоит играть в азартные игры с дьяволом.

[Вероника99]

http://dropmefiles.com/8vaEi

[FPaul]

Вероника99, а результаты - распечатать GR, D, C.

	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<<"\n D[i][j] "<<D[i][j]<<endl;
				
			cout<<"  "<<i+1<<"  "<<C[i][j]<<" "<<j+1<<endl;
		}

давай упростим в FU условие до

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

в FU изменим инициализацию C

	for (k=0; k<V; k++)
	for (i=0; i<V; i++)
		{C[k][i]=k;} <------ на просто k - т.к. физический смысл C[][] - номер вершины, а они от 0

RestorePath

int C[5][5];   <------- нужно избавиться от глобальных переменных
 int h[100];
 int y;
void RestorePath(int a,int b,int D[][5],int C[][5])
{
cout<<"\nRestorePath";
	if (a == b)
		return;  <--- здесь сообщение о том, что A==B
            if (D[a, b]==0)
                сообщение об отсутствии пути между A и B <------ 
		int stk[100] ;
		 stk[0]=b;
 int len=1;
 y=b;
  {
	  y=C[a][y];
    stk[len++]=y; //помещаем очередной узел в стек
  }while(y!=b);
// извлекаем узлы в обратном порядке
  for(i=len; i>0; i--) 
	  cout<< "  "<<stk[i-1];
  cout<<endl;
}

--------------
Offtop Если можно автоматически отформатировать исходник - пожалуйста, форматни.

[Poma][a]

// spysok_sumig.cpp: определяет точку входа для консольного приложения.
//



#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV = 1000;
int i, j, n = 5;
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 C[5][5];
int h[100];
int y;
void RestorePath(int a, int b, int D[][5], int C[][5])
{
	cout << "\nRestorePath";
	if (a == b)
		return;
	/*for (int i = 0; i < sizeof(D); i++)
		if (D[a][i] + C[i][b] == D[a][b])
		{
		cout << i + 1 << " ";
		RestorePath(a, i, D, C);
		return;
		}*/

	int stk[100];
	stk[0] = b;
	int len = 1;
	y = b;
	{
		y = C[a][y];
		stk[len++] = y; //помещаем очередной узел в стек
	}while (y != b);
	// извлекаем узлы в обратном порядке
	for (i = len; i > 0; i--)
		cout << "  " << stk[i - 1];
	/*y=C[i][j];
	if(D[i][y]!=0)
	cout<<"   "<<D[i][y];
	else RestorePath(D,i, y);

	if(D[y][j]!=0)
	cout<<"   "<<D[y][j];
	else RestorePath(D,y, j);*/
	cout << endl;
}
//алгоритм Флойда-Уоршелла
void FU(int D[][5], int V, int a, int b)
{

	int k;
	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 + 1;
			//cout<<" C[k][i] "<<C[k][i]<<endl;
		}
	for (k = 0; k < V; k++)
		for (i = 0; i < V; i++)
		{
			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 << "\n D[i][j] " << D[i][j] << endl;

						cout << "  " << i + 1 << "  " << C[i][j] << " " << j + 1 << endl;
					}
		}
	/*	for (k=0; k<V; k++)
		for (i=0; i<V; i++)
		for (j=0; j<V; j++)
		{
		cout<<" "<<C[j][k];
		if(j=C[j][k])
		break;

		}*/

	RestorePath(a, b, D, C);
	cout << "Путь между :" << a << " та " << b << endl;
	if (D[a - 1][b - 1] == 0)
		cout << "не существует" << endl;
	else
		cout << "  " << D[a - 1][b - 1];

	cout << endl;
	for (int k = 0; k < V; k++)
		for (int i = 0; i < V; i++)
			cout << " C[i][j] " << C[k][i] << endl;
}
//главная функция
void main()
{
	setlocale(LC_ALL, "Rus");
	int a, b;

	for (i = 0; i < n; i++)
	{
		for (j = 0; j<n; j++)

			cout << "  " << GR[i][j];
		cout << endl;
	}

	cout << "Введите две вершины" << endl;
	cin >> a >> b;
	if (a>n || b > n)
		cout << "Номер вершины не может быть больше за общее кол-во " << endl;
	cout << "Матрица кратчайших путей:" << endl;
	FU(GR, n, a, b);
	system("pause>>void");
}

А так.. Я бы забил вывод пути с помощью доп. матрицы..
Сложность алгоритма - куб.. Эта матрица нам ровным счетом погоды не делает..
А без не нее, может понятнее

[FPaul]

Sorry, это я так предложил

  {
	  y=C[a][y];
    stk[len++]=y; //помещаем очередной узел в стек
  }while(y!=b);   <--------- y!=a

Poma][a, а что ты изменил?
Там все матрицы что-то делают. D - хранит минимальную "стоимость проезда" между вершинами. C - хранит в сжатом виде все пути между вершинами. Если это не хранить, то для каждой новой пары вершин опять надо всё пересчитывать O(n^3).

[Вероника99]

Poma][a,матрица С для путей,еще одну матрицу сделать? И как потом все реализовать?

[Вероника99]

Так что делать?