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

[FPaul]

Я отвечу за ТС: "Да, ведь в этом то и весь смысл, т.к. "откуда" и "куда" задаётся в условии".

[Вероника99]

FPaul,насколько я понимаю,эту функцию нужно вызывать в цикле Флойда и наверное еще передавать саму матрицу?

...
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;
				RestorePath(D,i, j);
			
		}
...
void RestorePath(int D[][5],int i, int j)
{
	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);
}

[FPaul]

Не буду обманывать. Я плоховато знаком с теорией графов. Но то, что я прочитал по приведённым мною ссылкам, думаю, интерпретировать так:
- есть матрица смежности с весами путей d.
- вызываем алгоритм Флойда-Уэшелла и на выходе получаем две матрицы d_mod (с вычисленными минимальными длинами путей) и p (с информацией для восстановления пути).
Из этого вывод: поиск пути выполняется после завершения алгоритма Ф-У ( смешное название), сколько угодно раз и в любом месте программы (но обязательно после Ф-У).

[Вероника99]

FPaul, проанализирую все действия,которые я делаю с матрицей С.
1. До цикла Флойда присваиваю ей значения k

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

2. Во время цикла Флойда при нахождении минимального элемента:
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;
				
			
		}

3.После завершения цикла вызываю рекурсивную функцию

for (i=0; i<V; i++)
	for (j=0; j<V; j++)
	RestorePath(D,i, j);
...
void RestorePath(int D[][5],int i, int j)
{
	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);
}

Изначально в матрице 0 там где нет путей.Но что-то не так с рекурсивной функцией.Я не очень понимаю принцип ее работы.

[FPaul]

Если ты делаешь лабу по ссылке из твоего первого поста, то там сказано

Прочитать из файла input.txt граф, заданный там списком ребер с весами. Подсчитать длины кратчайших путей из каждой вершины в каждую, вывести кратчайший путь между какой-либо парой вершин.

Что означает - после Ф-У задать пару вершин A и B, и вывести путь между ними, т.е. один раз (не в цикле) вызвать RestorePath(A, B) - ну, может быть, в вызове RestorePath будет больше параметров (обойдёмся без глобальных переменных).
По твоей ссылке даётся пояснение физического смысла массива C. Думаю, надо попробовать восстановить путь или циклом или рекурсией.
Я всё спихиваю на тебя, потому что у меня нет готовой проги для расчёта C и не могу экспериментально посмотреть на результат. И с языком C++ не дружу - паскалист.

[Вероника99]

Да,вот я с этим восстановлением путей никак разобраться не могу и в инете не нашла конкретного примера с кодом

[FPaul]

Для 1-го случая заполнения С

В этом случае значение массива C[j][k] после окончания алгоритма будет указывать вершину, предпоследнюю в пути от j к k, и восстановление пути будет возможно сделать простым циклом;

Т.е. хотя бы в обратном порядке вывести k, C[j][k],....,j - цикл закончится когда j=С[j,m]

[Poma][a]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void path(int a, int b, const vector<vector<int>>& v, const vector<vector<int>>& p)
{
	if (a == b)
		return;
	for (int i = 0; i < v.size(); i++)
		if (v[a][i] + p[i][b] == v[a][b])
		{
			cout << i + 1 << " ";
			path(a, i, v, p);
			return;
		}
}

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(n));

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

	vector<vector<int>> p = v;
	
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (v[i][j] * v[i][k] * v[k][j] != 0)
					v[i][j] = min(v[i][j], v[i][k] + v[k][j]);

	cout << "From 1 to " << n << " :  " << v[0][n - 1] << endl << "Path :  ";
	path(0, n - 1, v, p);

	return 0;
}

[FPaul]

Ну и я попробовал реализовать - только на Pascal.
За матрицу взял орграф из этого примера.

{Реализация алгоритма Флойда}
program FloydWarshall;

const
  n = 5; {количество вершин графа}
  INFINITY = MaxInt;
type
  Tvertex = array [0..n - 1, 0..n - 1] of integer;
const
  vertex: Tvertex =
    (
    (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)
    );

  procedure FloydWarshall(v: Tvertex; n: integer; var d, p: Tvertex);
  var
    i, j, k: integer;
  begin
    {
    матрицу веса дуги преобразуем в требуемый для алгоритма вид
    - если i=j, то d[i, j]:=0
    - если из i в j нет ребра, то d[i, j]:=INFINITY (бесконечности)
    - иначе d[i, j] равно весу ребра из i в j
    подготовим матрицу для восстановления пути p
    }
    for i := 0 to pred(n) do
      for j := 0 to pred(n) do
      begin
        if v[i, j] = 0 then
          v[i, j] := INFINITY;
        if i = j then
          v[i, j] := 0;
        p[i, j] := i;
      end;
    d := v;
    for k := 0 to pred(n) do
    begin
      for i := 0 to pred(n) do
      begin
        for j := 0 to pred(n) do
        begin
          if (d[i, k] <> INFINITY) and (d[k, j] <> INFINITY) then
          begin
            if (d[i, j] > d[i, k] + d[k, j]) then
            begin
              d[i, j] := d[i, k] + d[k, j];
              p[i, j] := p[k, j];
            end;
          end;
        end;
      end;
    end;
  end;

  procedure RestorePath(const D, P: Tvertex; n: integer; A, B: integer);
  var
    k: integer;
  begin
    if A = B then
    begin
      writeln('A path between the same vertexes is ', A);
      exit;
    end;
    if D[A, B] = INFINITY then
    begin
      writeln('There is not a path from vertex ', A, ' to vertex ', B);
      exit;
    end;
    Write('Path: <');
    Write(B: 4);
    k := B;
    repeat
      k := P[A, k];
      Write(k: 4);
    until k = A;
  end;

  procedure ShowMatrix(const M: Tvertex; n: integer);
  var
    i, j: integer;
  begin
    for i := 0 to pred(n) do
    begin
      for j := 0 to pred(n) do
      begin
        if M[i, j] <> INFINITY then
          Write(M[i, j]: 4)
        else
          Write('inf': 4);
      end;
      writeln;
    end;
  end;

var
  D, P: Tvertex;
begin
  FloydWarshall(vertex, n, D, P);
  writeln('Vertex:');
  ShowMatrix(vertex, n);
  writeln('Distance:');
  ShowMatrix(D, n);
  writeln('Path:');
  ShowMatrix(P, n);
  RestorePath(D, P, n, 3, 1);
end.

Только путь выводится в обратном порядке, но тут ТС разберётся.
Идея как и говорилось в методичке к 1 способу вычисления p[][]. И физический смысл совпадает. Поэтому при поиске пути "иду" назад от B к P[A, B], P[A, (P[A, B])], ..., A.
На Pascal цикл repeat-until прекращается после превращения в истину выражения k=A (аналог в C k==A).

[Вероника99]

Poma][a, я написала код по аналогии с вашим,вот что получилось . Можете посмотреть как в этом коде можно найти пути...

#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 y;
void RestorePath(int a,int b,int D[][5],int C[][5])
{

	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;
		}
	/*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);*/
}
//алгоритм Флойда-Уоршелла
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 (int i=1; i<=V; i++)
		cout<<"    "<<i<<"";
	
		cout<<endl;

		for (int i=1; i<=V; i++)
		cout<<"  "<<"_";
				cout<<endl;
	for (i=0; i<V; i++)
	
	{
		cout<<" "<<i+1<<" |";
		for (j=0; j<V; j++)
				
			cout<<D[i][j]<<"   ";
	
		cout<<endl;
		

	}

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


	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;
	FU(GR, n,a,b);
	system("pause>>void");
}