1.问题描述
给定一个带权有向图G=（V,E）,每条边的权值都是非负实数，另外，给定一个源点，计算从源点到其他各个顶点的最短路径长度
2.算法设计
步骤1.设置带权邻接矩阵C如果<u,x>属于E，令C[u][x]=<u,x>的权值，否则C[u][x]无穷大，用一维数组dis来记录从源点到各个顶点的最短路径长度，用一维数组p
记录某顶点到源点的最短路径上的该顶点的前驱顶点
步骤2.初始化，令集合S={u}，对于集合V-S中的所有顶点x，设置dis[x]=C[u][x],如果顶点i与源点相邻，设置p[i]=-1,否则p[i]=u
步骤3.在集合V-S中按照贪心来找到使得dis[x]具有最小值的顶点t，
步骤4.将顶点t加入集合S中，同时更新集合V-S
步骤5.如果集合V-S为空，算法结束，否则，继续步骤6
步骤6.对集合V-S中的所有与顶点t相邻的顶点x。如果dis[x]>dis[t]+C[t][x],则dis[x]=dis[t]+C[t][x]并设置p[x]=t
3.算法实现
#include<stdio.h>
#include<string.h>
#define INF 1000
#define N 100
int C[N][N];
float dis[N];aaaaaa
int p[N];
/*
n :节点个数。u:源点；C[n][n]：二维数组记录节点间的长度，
dis[]：记录某顶点到源点的最短路径长度，p：记录某顶点到源点
的最短路径上的该顶点的前驱顶点
*/
void Dijkstra(int n,int u)
{
bool s[N+1];//如果s[i]等于true，说明顶点i已加入集合S中，否则顶点i属于集合V-S
int i,j;
for(i=1;i<=n;i++)
{
dis[i]=C[u][i];//初始化各个顶点到源点的最短路径长度
s[i]=false;
if(dis[i]==INF)
p[i]=-1; //说明顶点i与源点不相邻
else
p[i]=u;//说明顶点i与源点相邻
}
dis[u]=0;
s[u]=true;//初始时，集合S中只有一个元素：源点
for(i=1;i<=n;i++)
{
int temp=INF;
int t=u;
for(j=1;j<=n;j++)//在集合V-S中找到距离源点最近的顶点t
{
if((!s[j])&&dis[j]<temp)
{
t=j;
temp=dis[j];
}
}
s[t]=true;//把t加入集合S中
for(j=1;j<=n;j++)
{
if((!s[j])&&C[t][j]<INF)
{
if(dis[j]>(dis[t]+C[t][j]))//如果新距离比原距离短，就更新
{
dis[j]=dis[t]+C[t][j];
p[j]=t;//前驱节点更新
}
}
}
}
}
int main()
{
int i,j,n,u,num;
printf("输入节点数：\n");
scanf("%d",&n);
printf("输入源点（序号）：\n");
scanf("%d",&u);
printf("输入边数：\n");
scanf("%d",&num);
for(i=1;i<=n;i++) //为dis[]数组赋初值Max
{
for(j=1;j<=n;j++)
{
C[i][j]=INF;
}
}
for(i=1;i<=num;i++)
{
int x,y;
printf("输入始节点：\n");
scanf("%d",&x);
printf("输入末节点：\n");
scanf("%d",&y);
printf("输入赋予边的权值：\n");
scanf("%d",&C[x][y]);
printf("边的(%d,%d)权值为：%d\n",x,y,C[x][y]);
}
Dijkstra(n,u);
for(i=1;i<=n;i++)//输入源点到各顶点的最短路径
{
if(i!=u)
printf("源点%d到顶点%d的最短路径值为%f\n",u,i,dis[i]);
}
}