If your strcuture should only represent the shortest path, then it shoul dbe ok. If you need to represent the graph with it, then I don't see how you can represent it, because edges can have multiple edges connecting each other. So you would need an array and a counter to keep track of the edges per vertex.
Are my structs set up correctly for adding cities (vertices) to an undirected weighted graph to find shortest path?
Pregunta
Hello I've made a program to calculate the distances between two cities and now I want to use the data to map the cities on a undirected weighted graph. Then it will use Dikstra's Algorithm to find the shortest path. I'm trying out a adjacency list implementation because it seemed the right way but if another way is easier I'll do that. In some cases a city will have three neighbors.
This is the file I'm reading from, distances.txt: I was having a little trouble reading in city names with two words so I assigned them a integer ID but will probably change it later once I figure that out.
//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
This is my program:
#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() {
}
Solución
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow