136 lines
2.8 KiB
C++
136 lines
2.8 KiB
C++
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
|
|
#define MAX_V 100 /*最大節點數*/
|
|
#define Infinite 1073741823
|
|
|
|
long int dist[MAX_V+1][MAX_V+1];
|
|
int N; // 節點數量
|
|
int source, sink; // 起點和終點
|
|
|
|
void init();
|
|
bool floydWarshall();
|
|
void output_path();
|
|
void output_step();
|
|
|
|
int main() {
|
|
|
|
init();
|
|
|
|
// 檢查是否存在負權迴路
|
|
if (floydWarshall()) {
|
|
output_path();
|
|
printf("\n圖形中存在負權迴路，無法計算最短路徑\n");
|
|
} else {
|
|
output_path();
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void init(){
|
|
FILE *fptr;
|
|
int i, j, weight;
|
|
|
|
fptr = fopen("shortestPath.dat", "r");
|
|
if (fptr == NULL) {
|
|
perror("shortestPath.dat");
|
|
exit(1);
|
|
}
|
|
|
|
fscanf(fptr, "%d", &N); // 讀取圖形節點數
|
|
|
|
// 初始化距離矩陣
|
|
for (i = 1; i <= N; i++) {
|
|
for (j = 1; j <= N; j++) {
|
|
if (i == j)
|
|
dist[i][j] = 0; // 自身到自身的距離為0
|
|
else
|
|
dist[i][j] = Infinite; // 其他預設為無窮大
|
|
}
|
|
}
|
|
|
|
// 讀取邊的權重
|
|
while (fscanf(fptr, "%d %d %d", &i, &j, &weight) != EOF)
|
|
dist[i][j] = weight; // 設置直接相連邊的權重
|
|
|
|
|
|
fclose(fptr);
|
|
printf("檔案內權重如下\n");
|
|
output_step();
|
|
|
|
printf("\n輸入起始節點 (1~%d): ", N);
|
|
scanf("%d", &source);
|
|
printf("輸入目標節點 (1~%d): ", N);
|
|
scanf("%d", &sink);
|
|
}
|
|
|
|
bool floydWarshall(){
|
|
int k, i, j;
|
|
|
|
// Floyd Warshall 核心演算法
|
|
for (k = 1; k <= N; k++) {
|
|
for (i = 1; i <= N; i++) {
|
|
for (j = 1; j <= N; j++) {
|
|
// 如果經過 k 點的路徑比直接路徑短，更新距離
|
|
if (dist[i][k] != Infinite &&
|
|
dist[k][j] != Infinite &&
|
|
dist[i][k] + dist[k][j] < dist[i][j]) {
|
|
dist[i][j] = dist[i][k] + dist[k][j];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// 檢查是否存在負權迴路
|
|
for (i = 1; i <= N; i++) {
|
|
if (dist[i][i] < 0) {
|
|
return true; // 存在負權迴路
|
|
}
|
|
}
|
|
|
|
return false; // 不存在負環
|
|
}
|
|
|
|
|
|
void output_step(){
|
|
int i, j;
|
|
|
|
// 輸出標題列
|
|
printf("\t");
|
|
for (j = 1; j <= N; j++) {
|
|
printf("V%d\t", j);
|
|
}
|
|
printf("\n");
|
|
|
|
// 輸出距離矩陣
|
|
for (i = 1; i <= N; i++) {
|
|
printf("V%d\t", i);
|
|
for (j = 1; j <= N; j++) {
|
|
if (dist[i][j] == Infinite)
|
|
printf("∞\t");
|
|
else
|
|
printf("%2ld\t", dist[i][j]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
void output_path(){
|
|
int i, j;
|
|
|
|
// 輸出標題列
|
|
printf("\n節點間最短距離矩陣：\n");
|
|
|
|
output_step();
|
|
|
|
// 檢查起點到終點的路徑
|
|
if (dist[source][sink] == Infinite) {
|
|
printf("\n節點 V%d 到節點 V%d 沒有路徑\n", source, sink);
|
|
} else {
|
|
printf("\n從節點 V%d 到節點 V%d 的最短距離為：%ld\n",
|
|
source, sink, dist[source][sink]);
|
|
}
|
|
}
|