c - 我的结构设置是否正确，可以将城市(顶点)添加到无向加权图中以找到最短路径？

Question

您好，我编写了一个程序来计算两个城市之间的距离，现在我想使用这些数据将城市映射到无向加权图上。然后它将使用 Dikstra 算法来找到最短路径。我正在尝试邻接列表实现，因为它似乎是正确的方法，但如果另一种方法更容易，我会这样做。在某些情况下，一个城市会有三个邻居。

这是我正在读取的文件 distances.txt:我在读取包含两个单词的城市名称时遇到了一些困难，因此我为它们分配了一个整数 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() {

}

Answer 1

如果你的结构应该只代表最短路径，那么它应该没问题。如果您需要用它来表示图形，那么我不知道如何表示它，因为边可以有多个相互连接的边。因此，您需要一个数组和一个计数器来跟踪每个顶点的边。