c++ - FloydWarshall 无限

问题描述

我是编程的业余爱好者。我试图展示该算法的每个步骤，但我想在每个 D 矩阵上将 1000 表示为 INF。

需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交需要更多行提交

#include <iostream>
#include <limits>
#define INF 1000

using namespace std;

/* my example matrix is 
0  3  inf  7
8  0   2  inf
5 inf  0   1
2 inf inf  0

i want to write that each D matrix show 1000 as INF
*/

void FloydWarshall(int **dist, int V){

int i,j,k;

for(k = 0; k < V; k++){
cout<<"D"<<k<<" matrix is: "<<endl;

for(i = 0; i < V; i++){

    for(j = 0; j < V; j++){
        cout<<dist[i][j]<<"     ";
        if(dist[i][k] != INF && dist[j][k] != INF && dist[i][j] > (dist[i][k] + dist[k][j]))
                dist[i][j] = dist[i][k]+dist[k][j];  
                          } 
                cout<<"  "<<endl;
                      }
                cout<<"  "<<endl;
                  }     


for(i = 0; i < V; i++){ 
    for(j = 0; j < V; j++){
        cout<<" "<<endl;
        cout<<"Shortest path between "<<i<<" and "<<j<<" is : "<<endl;
        if(dist[i][j]==INF)
                cout<<"INF"<<endl;
        else
                cout<<dist[i][j]<<endl;
                          } 
                      }    

   }

int main(){


int i,j,n;
int **dist;
int *cost;

cout<<"Please, enter the number of vertices: "<<endl;
cin>>n;

dist = new int*[n];

for(i = 0;i < n; i++){
dist[i] = new int[n];
}

cout<<"Please, enter the adjacency matrix: "<<endl;
cout<<"Do not forget "<<INF<<" if there is no connection between two vertices"<<endl;
for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
        cin>>dist[i][j];
        if (dist[i][j] == 0 && i != j){
            dist[i][j] = INF;
 }
 }
 }
cout<<"  "<<endl;

FloydWarshall(dist,n);
cout<<" "<<endl;
cout<<"     The Distance Matrix is:     "<<endl;
  for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
 {
      cout<<dist[i][j]<<"     ";
 }
cout<<"\n";
 }
return 0;
 }

标签： c++algorithmfloyd-warshall

c++ - FloydWarshall 无限

问题描述

解决方案

推荐阅读