Floyd-Warshall算法实现不起作用

我正在为一个赋值实现Floyd-Warshall算法，并且输出矩阵不正确。我在网上对其他人的算法进行了双重检查，看起来和其他人一样。我只是想念一些东西？任何帮助表示赞赏。Floyd-Warshall算法实现不起作用

我输入文件是：

的结果矩阵应该是：

的路径矩阵应该是：

我收到我的结果矩阵：

-4 -3 -2 -5 

-5 -4 -3 -6 

-6 -5 -4 -7 

-7 -6 -5 -8

而对于路径矩阵：

这里是我的程序代码：

#include <iostream> 
#include <fstream> 
#include <vector> 
#include <string> 
#include <iomanip> 

using namespace std; 

// Forward Declarations 
void readFile(); 
void fillPathWithZeros(); 
void findFloydsAlgorithmMatrix(); 
void printGraph(vector< vector<int> >& inVector, string heading); 

int size; 
vector< vector<int> > M; // Matrix with weights 
vector< vector<int> > P; // Path Matrix 

int main() 
{ 
    readFile(); 
    fillPathWithZeros(); 
    findFloydsAlgorithmMatrix(); 

    cin.get(); 
    return 0; 
} 

void readFile() 
{ 
    int z = 0; 

    ifstream file("example.txt", fstream::in); // File name is example.txt 
    if (file.is_open()) 
    { 
     // read characters by using "file >>" 
     file >> z; 
     size = z; 
     vector< vector<int> > fileGraph(size, vector<int>(size)); // creates a local 2D vector to size stated in file 
     for (int i = 0; i < size; i++) 
     { 
      for (int j = 0; j < size; j++) 
      { 
       file >> fileGraph[i][j]; 
      } 
     } 

     M = fileGraph; // Copies the local vector to a global vector to be used in other functions 
     printGraph(fileGraph, "Input matrix M: "); // Print out the input Matrix 
    } 


} 

// Initialize the Path Vector with all 0's 
void fillPathWithZeros() 
{ 
    vector< vector<int> > localPathGraph(size, vector<int>(size)); 

    for (int i = 0; i < size; i++){ 
     for (int j = 0; j < size; j++) { 
      localPathGraph[i][j] = 0; 
     } 
    } 

    P = localPathGraph; // set the local Path Vector to the Global Path Vector 
} 

void findFloydsAlgorithmMatrix() 
{ 

    for (int k = 0; k < size; k++) { 
     for (int i = 0; i < size; i++) { 
      for (int j = 0; j < size; j++){ 
        if ((M[i][k] + M[k][j]) < M[i][j]) { 
         M[i][j] = M[i][k] + M[k][j]; 
         P[i][j] = k + 1; 
        } 
      } 
     } 
    } 

    printGraph(M, "Resultant matrix M: "); 
    printGraph(P, "Path matrix P: "); 

} 

void printGraph(vector< vector<int> >& inVector, string heading){ 

    cout << heading << endl; 

    for (int i = 0; i < size; i++){ 
     for (int j = 0; j < size; j++) { 
      cout << setw(2) << inVector[i][j] << " "; 
     } 
     cout << endl; 
    } 
    cout << endl; 
}

来源

2014-03-04 Mopikope

1）调用readFile（）之后，你确定输入收到了好吗？ 2）将矩阵初始化为0的循环不需要写入。只需使用vector的构造函数：'vector < vector> localPathGraph（size，vector （size，0））;' – PaulMcKenzie

For＃1输入正在接收OK。我将它添加到readFile（）中的矢量后立即打印出来。这很好。对于＃2我不知道，谢谢你告诉我。 – Mopikope

1）你确定矩阵中没有负循环吗？弗洛伊德 - 华沙不适用于负周期。看到这里：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm 对于测试，尝试一个3×3或甚至2×2矩阵，只使用正数。看着你的代码，它似乎没问题（有些东西可以清理，但这是另一回事）。 – PaulMcKenzie

矩阵中有负距离。 Floyd-Warshall不支持负距离或周期。

在这里看到：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

至于你的代码去，它看起来确定从算法的角度来看。有些东西可以用较短的代码完成（例如向量的初始化），但除此之外，如果矩阵不具有负距离/周期，代码应该工作。

来源

2014-03-04 10:05:31 PaulMcKenzie

Floyd-Warshall算法实现不起作用

回答

相关问题