最短路徑問題 
#include "datastru.h" 
#include <stdio.h> 
#include <malloc.h> 
#define MAX 10000 

MGRAPH create_mgraph(){ 
/*建立有向圖的鄰接矩陣結構*/ 
int i, j, k, h; 
MGRAPH mg; 

mg.kind = 3; 
printf("\n\n輸入頂點數和邊數(用逗號隔開) : "); 
scanf("%d,%d", &i,&j); 
mg.vexnum = i; /*存放頂點數在mg.vexnum中 */ 
mg.arcnum = j; /*存放邊點數在mg.arcnum中*/ 
fflush(stdin); 
for(i = 0; i < mg.vexnum; i++) 
{ printf("輸入頂點 %d 的值 : ",i + 1); /*輸入頂點的值*/ 
scanf("%d", &mg.vexs[i]); 
fflush(stdin);} 
for(i = 0; i < mg.vexnum; i++) /*鄰接矩陣初始化*/ 
for(j = 0; j < mg.vexnum; j++) 
mg.arcs[i][j] = MAX; 
for(k = 1; k <= mg.arcnum; k++) 
{ printf("輸入第 %d 條邊的起始頂點和終止頂點(用逗號隔開): ",k); 
scanf("%d,%d",&i,&j); /*輸入弧的起始頂點和終止頂點*/ 
fflush(stdin); 
while(i < 1 || i > mg.vexnum || j < 1 || j > mg.vexnum) 
{ printf("輸入錯，重新輸入: "); 
scanf("%d,%d", &i, &j);} 
printf("輸入此邊權值 : "); /*輸入弧上之權值*/ 
scanf("%d", &h); 
mg.arcs[i - 1][j - 1] = h;} 
return mg; 
} 

main() 
{ 
MGRAPH mg; 
int cost[MAXLEN][MAXLEN]; 
int path[MAXLEN], s[MAXLEN]; 
int dist[MAXLEN]; 
int i, j, n, v0, min, u; 

printf("\n求有向圖單源點最短路徑\n"); 
mg = create_mgraph(); /*建立有向圖的鄰接矩陣結構*/ 
printf("\n\n起始頂點為 : "); /*有向圖中頂點的編號從1編起*/ 
scanf("%d", &v0); 
v0 --; 
n = mg.vexnum; 
for(i = 0; i < n; i++) /*cost矩陣初始化*/ 
{for(j = 0; j < n; j++) 
cost[i][j] = mg.arcs[i][j]; 
cost[i][i] = 0;} 
for(i = 0; i < n; i++) 
{dist[i] = cost[v0][i]; /*dist數組初始化*/ 
if(dist[i] < MAX && dist[i] > 0) /*path數組初始化*/ 
path[i] = v0;} 
for(i = 0; i < n; i++) /*s數組初始化*/ 
s[i] = 0; 
s[v0] = 1; 
for(i = 0; i < n; i++) /*按最短路徑遞增算法計算*/ 
{ min = MAX ; 
u = v0; 
for(j = 0; j < n; j++) 
if(s[j] == 0 && dist[j] < min) 
{min = dist[j]; 
u = j;} 
s[u] = 1; /*u頂點是求得最短路徑的頂點編號*/ 
for(j = 0; j < n; j++) 
if(s[j] == 0 && dist[u] + cost[u][j] < dist[j])/*調整dist*/ 
{dist[j] = dist[u] + cost[u][j]; 
path[j] = u;} /*path記錄了路徑經過的頂點*/ 
} 
for(i = 0; i < n; i++) /*打印結果*/ 
if(s[i] == 1) 
{u = i; 
while(u != v0) 
{printf("%d <- " , u + 1); 
u = path[u];} 
printf("%d ", u + 1); 
printf(" d = %d\n", dist[i]); /*有路徑*/ 
} 
else 
printf("%d <- %d d= MAX\n ", i + 1, v0 + 1);/*無路徑*/ 
printf("\n\n"); 
}