1
Dijkstra의 알고리즘을 사용하여 하나의 정점에서 다른 정점으로의 최단 경로 비용을 얻는 코드가 있습니다. 첫 번째 행의 정점 수를 포함하는 텍스트 파일을 읽습니다. 나머지 파일은 비용 인접 행렬입니다. 또한 꼭지점 사이를 오가는 실제 경로를 가져와야하지만 그 부분을 파악할 수는 없습니다. 내 코드는 아래와 같습니다. 경로를 점점Dijkstra 알고리즘의 실제 경로 얻기
3
0 3 1
1 0 4
1 2 0
도와주세요 :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
FILE *fp;
typedef enum { false, true } bool; //creating a "bool" data type
void readFromFile(char *out){ //reading from file
fgets(out, 1000, fp);
}
void loadFile(){ //loading file
fp = fopen("graphmatrix.txt","r");
if(fp==NULL){
printf("graphmatrix.txt not found.\n");
exit(1);
}
}
void convertToInt (char *arr, int *matrix) { //parsing lines from text file into int array
int num, i = 0, len;
while (sscanf(arr, "%d%n", &num, &len) == 1) {
matrix[i] = num;
arr += len;
i++;
}
}
void dijkstra(int src, int vertices, int graph[vertices][vertices]) { //dijkstra's algo
int i;
int count;
int v;
int dist[vertices]; //will hold the shortest distances (so far) from source to vertex
int pred[vertices][vertices];
int predCount = 0;
bool sptSet[vertices]; //sptSet[i] will be true if vertex i is done processing (in class 1)
//initialize all distances as infinity (int_max) and stpSet[] as false (in class 2)
for (i = 0; i < vertices; i++){
dist[i] = INT_MAX;
sptSet[i] = false;
pred[i][i] = INT_MAX;
}
dist[src] = 0; //distance from source to itself is 0
for (count = 0; count < vertices - 1; count++) { //gets shortest distances
printf("**COUNT = %d**\n", count + 1);
int u = minDistance(dist, sptSet, vertices);
printf("u = %d\n", u);
sptSet[u] = true; //marks current vertex as done
for (v = 0; v < vertices; v++) { //updates distances
printf("in count %d, v = %d\n", count, v);
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){
dist[v] = dist[u] + graph[u][v];
printf("dist[%d] = %d\n", v, dist[v]);
pred[count][predCount] = u;
predCount++;
}
}
}
printSolution(dist, vertices, src, pred[src]);
}
int minDistance(int dist[], bool sptSet[], int vertices) { //checks if new distance is smaller than current distance
int min = INT_MAX, min_index;
int v;
printf("\n---minDistance function---\n\n");
for (v = 0; v < vertices; v++){
printf("v = %d\n", v);
if (sptSet[v] == false && dist[v] <= min){
min = dist[v], min_index = v;
printf("min: %d\n", min);
printf("min_index: %d\n", min_index);
}
}
printf("\n---exit minDistance---\n\n");
return min_index;
}
int printSolution(int dist[], int vertices, int src, int pred[]) { //prints distance and path to screen
int i, j;
for (i = 0; i < vertices; i++){
printf("vertex %d to vertex %d: %d\n", src + 1, i + 1, dist[i]);
printf("path: ");
for (j = 0; j < vertices; j++){
printf("%d -> ", pred[j]);
}
}
}
int main(){
int i, j;
int vertices;
char tempvertices[10];
char temp;
loadFile();
readFromFile(tempvertices);
vertices = tempvertices[0] - '0';
char matrixLines[vertices][100];
int matrix[vertices][vertices];
for (i = 0; i < vertices; i++){
readFromFile(matrixLines[i]);
convertToInt(matrixLines[i], matrix[i]);
}
for (j = 0; j < vertices; j++){
printf("\n-----------------DIJKSTRA number %d-------------------\n\n", j + 1);
dijkstra(j, vertices, matrix);
}
return 0;
}
샘플 텍스트 파일 (이름 graphmatrix.txt) : 당신이 볼 수 있듯이, 나는 적절한 이전 데이터 구조를 작성하는 데 실패?