0

フロイドのアルゴリズムを実装しようとしています。私のコードには、理解できない問題があると思います。出力は異なります。それらは、いくつかの小さなものが欠けているだけです。以下のコードには、入力、出力、および元の出力も含まれています。少しでもお役に立てば幸いです。

#include<stdio.h>
#define maxVertices   12
#define INF 55
int min(int a,int b){
    return (a<b)?a:b;
}
void init(int distance[maxVertices][maxVertices]){
    int iter,jter;
    for(iter=0;iter<maxVertices;iter++){
            for(jter=0;jter<maxVertices;jter++){
                    if(iter==jter){
                            distance[iter][jter] = 0;
                    }
                    else{
                            distance[iter][jter] = INF;
                    }
            }
    }}
void FloydWarshall(int distance[maxVertices][maxVertices],int vertices){ 
 int k,i,j;
          for(k=0;k<vertices;k++){
            for(i=0;i<vertices;i++){
                    for(j=0;j<vertices;j++){
                       if(distance[i][j] > distance[i][k] + distance[k][j])
            distance[i][j] = distance[i][k] + distance[k][j];
                     }
             }
     }
 }

int main(){
int i,j;    
    int graph[maxVertices][maxVertices];
    int distance[maxVertices][maxVertices];
    int vertices,edges,iter,jter;
    /* vertices represent number of vertices  in the graph. */
         scanf("%d",&vertices);
    /*initialize distance between all pairs as infinity*/
        init(distance);
    int vertex1,vertex2,weight;
    /* Here graph[i][j] represent the weight of edge joining i and j */
    for(iter=0;iter<11;iter++)
    {
            scanf("%d%d%d", &vertex1, &vertex2, &weight);
            graph[vertex1][vertex2] = weight;
            distance[vertex1][vertex2] = weight;
    }
     FloydWarshall(distance,vertices);  
    return 0;}
  /*
 8                       MY INPUT
 1 2 6
 2 1 6
1 6 10
2 6 3
3 2 8
4 5 9
5 4 9
5 7 7
6 1 10
6 2 3
7 5 7

  0  1  2  3  4  5  6  7    MY OUTPUT
0-0 55 55 55 55 55 55 55    
1-55 0 6 55 55 55  9  55 
2-55 6 0 55 55 55  3  55 
3-55 14 8 0 55 55 11 55 
4-55 55 55 55 0 9 55 16         
5-55 55 55 55 9 0 55 7 
6-55 9 3 55 55 55 0 55 
7-55 55 55 55 16 7 55 0 

************************
   0 1  2  3  4  5  6  7      THE ORIGINAL OUTPUT
 0-0 55 55 55 55 55 55 55 
 1-55 0 6 14 55 55 9 55 
 2-55 6 0  8 55 55 3 55 
 3-55 14 8 0 55 55 11 55    
 4-55 55 55 55 0 9 55 16 
 5-55 55 55 55 9 0 55 7 
 6-55 9 3 11 55 55 0 55 
 7-55 55 55 55 16 7 55 0

*/

4

1 に答える 1

2

2 3 8入力データが不足していると思います。または、追加することにより、重みを強制的に対称にすることができます

distance[vertex2][vertex1] = weight;

後

distance[vertex1][vertex2] = weight;
于 2012-06-10T16:47:08.717 に答える