东华大学计算机学院离散数学
实验五：最短路径
实验所属系列：离散数学课后实验
实验对象：本科
相关课程及专业：离散数学，计算机专业
实验类型：课后实验
实验时数（学分）：4学时
实验目的
学习图的最短路径算法的实现。

实验内容与要求
根据输入的图形（实验四），输入起点和终点，求出最短路径和最短路径的长度。

实验的软硬件环境
PC机一台，装有VC++6.0或其它C语言集成开发环境。

实验准备
熟悉最短路径算法。

实验步骤
1．编写一段代码，接收键盘的输入定点的数量，并以输入的整数对作为边来建立图形的邻接矩阵（无向权重图）。

例如：5，6，12
表示定点5和定点6间有边，边的权重为12。

2 打印出邻接矩阵。

3．输入起点和终点。

4、打印最短路径和最短路径的长
#include<stdio.h>
#define BIG 9999
void dijkstra(int cost[][6],int n,int st,int distance[])
{
int s[6];
int mindis,dis;
int i,j,u;
for(i=0;i<n;i++)
{
distance[i]=cost[st][i];
s[i]=0;
}
s[st]=1;
for(i=0;i<n;i++)
{
mindis=BIG;
for(j=0;j<n;j++)
{
if(s[j]==0&&distance[j]<mindis)
{
mindis=distance[j];
u=j;
}
}
for(j=0;j<n;j++)
{
if(s[j]==0)
{
dis=distance[u]+cost[u][j];
distance[j]=(distance[j]<dis)?distance[j]:dis;
}
}
s[u]=1;
}
}
void main()
{
int y,j;
char *vertex[6]={"V1","V2","V3","V4","V5","V6"};
int cost[6][6];
for(y=0;y<6;y++)
{
for(j=0;j<6;j++)
{
cost[y][j]=BIG;
}
}
int start,end,weight,i;
printf("input start&end&weight:");
for(i=0;weight!=0;i++)
{
scanf("%d,%d,%d",&start,&end,&weight);
cost[start-1][end-1]=weight;
cost[end-1][start-1]=weight;
}
int distance[6];
int s,e;
printf("input start-vertex &&end-vertex(no more than 6):");
scanf("%d,%d",&s,&e);
dijkstra(cost,6,s-1,distance);
printf("%s---->%s %d\n",vertex[s-1],vertex[e-1],distance[e-1]);
}
数据测试
输入：
1，3，5
1，4，30
2，1，2
3，2，15
3，6，7
5，4，4
6，4，10
6，5，18
计算1，5两点之间距离
输出：。