Floyd-Warshall实现

Question

我对弗洛伊德-沃肖尔算法有个问题。如果输入的顶点超过4个，则不起作用。为了制作二维动态数组，我制作了一个动态数组N*N并访问Ai，j= A(i-1)*N+j

void floyd_Algorithm(fstream &F2,int N,int matrixGraph[],int matrixP[])
{
for (int k=1; k<=N; k++)
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
        {
            if (matrixGraph[(i-1)*N+j] > matrixGraph[(i-1)*N+k] + matrixGraph[(k-1)*N+j])
            {
                matrixGraph[(i-1)*N+j] =  matrixGraph[(i-1)*N+k] + matrixGraph[(k-1)*N+j];
                matrixP[(i-1)*N+j] = k ;
            }
}

这是4个顶点矩阵的输入

4.

0 10 6 2| 10 0 53|6 5 0 1| 2 3 1 0|

输出

0 5 3 2

5 0 4 3

3 4 0 1

2 3 1 0

1 4 4 1

4 2 4 2

4 4 3 3

4 4 4

7个顶点矩阵输入

7

0 3 6 0 0 0| 3 0 2 4 0 0 0| 6 2 0 1 4 2 0| 0 4 1 0 2 0 4| 0 0 4 2 0 2 1| 0 0 2 0 2 0 1| 0 0 0 4 1 1 0

输出

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

1 5 7 1 1 1

5 2 7 5 2 2 2

7 7 3 7 7 7 3

4 5 7 4 1 4 1

5 5 7 1 5 1 1

6 6 7 6 1 6 1

7 7 7 1 1 1 7

Answer 1

你的索引有问题。

如果你的顶点是1 <= v <= N的角度，那么i和j之间的路径应该是矩阵(i-1)*N+j-1

为了避免错误，您可能应该将折点保持在0 <= v< N的范围内，对于(int i= 0；i< N；i++)，matrixi*N+j

Answer 2

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <fstream>
#include <vector>
using namespace std;

void floyd_Algorithm(fstream &F2,int N,int matrixGraph[],int matrixP[])
{
for (int k=0; k<N; k++)
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
        {
            if (matrixGraph[i*N+j] > matrixGraph[i*N+k] + matrixGraph[k*N+j])
            {
                matrixGraph[i*N+j] =  matrixGraph[i*N+k] + matrixGraph[k*N+j];
                matrixP[i*N+j] = k ;
            }
}
cout << "Ma tran duong di ngan nhat sau khi xu ly :\n";
for (int i=0; i<N; i++)
{
    cout <<"\n";
    for (int j=0; j<N; j++)
        cout << matrixGraph[i*N+j] <<"   ";
}
cout << "\nMa tran luu dinh sau khi xu ly :\n";
for (int i=0; i<N; i++)
{
    cout <<"\n";
    for (int j=0; j<N; j++)
        cout << matrixP[i*N+j] <<"   ";
}
}
void dijkstra_Algorithm(fstream &F2,int N,int matrixGraph[],int matrixP[])
{

}
int main()
{
int n,t,c;
fstream f1,f2;
f1.open("D:\\Input3.INP",ios::in);
f2.open("D:\\Output3.OUT",ios::out);
f1 >> n;
int matrix_graph[n*n];
for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
        f1 >> matrix_graph[i*n+j];
    }
int matrix_p[n*n];
for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
        matrix_p[i*n+j] = i;
    }
cout << "Hay nhap thuat toan muon su dung :\n";
cout << "1 : Floyd-Warshall Algorithm\n";
cout << "2 : Dijkstra Algorithm\n";
while ((t!=1)&&(t!=2))
{
    cout << "Enter : ";
    cin >> t;
}
cout << "Ma tran trong so da nhap la :\n";
for (int i=0; i<n; i++)
{
    cout <<"\n";
    for (int j=0; j<n; j++)
        cout << matrix_graph[i*n+j] <<"   ";
}
cout << "\n";
switch (t)
{
case 1 :
    floyd_Algorithm(f2,n,matrix_graph,matrix_p);
    break;
case 2 :
    dijkstra_Algorithm(f2,n,matrix_graph,matrix_p);
    break;
}
return 0;
}

我的完整代码在这里，更改索引仍然会产生相同的结果