最短路程.txt

【问题描述】 甲、乙、丙、丁、未五城市分别距离为( 单位是： km)： 甲 - 乙 300 甲 - 未 3000 乙 - 丙 2500 乙 - 丁 800 丙 - 未 1000 丁 - 甲

#include <stdio.h> 
#include <malloc.h> 
#define MAX 10000 
#define MAXLEN 40 
#define VEXTYPE int 
#define ADJTYPE int 

typedef struct 
{ 
VEXTYPE vexs[MAXLEN]; //顶点的信息 
ADJTYPE arcs[MAXLEN][MAXLEN];//邻接矩阵 
int vexnum,arcnum ; //顶点数和边数 
int kind; //有向网的kind=3 
}MGRAPH; 

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"); 
}