0

こんにちは、2 つの都市間の距離を計算するプログラムを作成しました。このデータを使用して、無向加重グラフに都市をマッピングしたいと考えています。次に、ディクストラのアルゴリズムを使用して最短経路を見つけます。正しい方法に思えたので、隣接リストの実装を試していますが、別の方法が簡単な場合はそうします。場合によっては、1 つの都市に 3 つの近隣都市が存在することがあります。

これは私が読んでいるファイル、distances.txt です。都市名を 2 つの単語で読むのに少し問題があったので、整数 ID を割り当てましたが、後でそれを理解したら変更する予定です。

//The first integer is city1 and the second integer is city2 followed by the 
//distance between the two
0 1 11541.187059  
2 3 3858.222989
4 5 833.098012
6 7 20014.000000
8 9 13960.338459
10 11 13468.406555

これは私のプログラムです：

#include <stdio.h>


typedef struct vertex vertex;
typedef struct edge edge;

struct vertex
{
    int ID;
    vertex* successor;
    vertex* predecessor;
};

struct edge
{
    double weight;
    vertex* vertexA;
    vertex* vertexB;
};


int main() {


    char line[256];
    FILE *fin = fopen("distances.txt","r"); 
    FILE *fout = fopen("shortest.txt","w"); 

    int c1,c2;
    double distance;

    vertex *city1,*city2; 

    while ( fscanf (fin, "%d %d %lf", &c1,&c2,&distance)== 3)
    {   
        printf("[City1: %d] [City2: %d] [Distance: %lf]\n",c1,c2,distance); 
        city1->ID = c1; 
        city2->ID = c2; 
        city1->successor = city2; 
        city2->predecessor = city1; 

    }

    return 0; 

}

void addEdge(vertex* x,vertex* y, double weight){
    edge* m; 
    m = malloc (sizeof(edge)); 
    m->weight = weight; 
    m->vertexA = x;
    m->vertexB = y; 

}

void shortestPath() {

}
4

1 に答える 1

0

構造体が最短パスのみを表す必要がある場合は、問題ありません。それを使用してグラフを表現する必要がある場合、エッジは互いに接続する複数のエッジを持つことができるため、それをどのように表現できるかわかりません。したがって、頂点ごとのエッジを追跡するには、配列とカウンターが必要になります。

于 2013-08-03T07:01:15.207 に答える