一、问题描述
给定一个随机带权有向图，每条边的权是一个实数。另外给定图中一个顶点，称为源。计算源到各顶点的最短路径长度（即距离），要求能随机生成图，随机指定源点计算出到顶点的最短距离。
二、解题思路
首先利用邻接矩阵定义一个随机有向图
其次利用迪克斯特拉算法求解源点到各个顶点的最短距离
最后利用回溯递归最短路径
迪克斯特拉算法：是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
三、解题过程
随机生成有向图
随机指定源点
迪克特拉斯算法
首先确定顶点总个数
从源到顶点以及顶点前一个点
找到特殊路径
更新dist值
输出最短路径
四、完整代码如下：
//【贪心算法】单源最短路径问题
#include
#include
const int N=5; //顶点个数
const int M=1000;
void Dijkstra(int n, int v, int dist[], int prev[], int c[][N+1])
{
bool s[N+1]; // 顶点集合s
//初始化
for (int i=1;i<=n;i++)
{
dist[i]=c[v][i]; // 从源到顶点i的最短特殊路径长度
s[i]=false;
if(dist[i]==M)
prev[i]=0; // 从源到顶点i的最短路径上前一个顶点
else
prev[i]=v;
}
dist[v]=0;
s[v]=true;
for(int i=1;i
int mindist=M;
int u=v;
// 找到具有最短特殊路长度的顶点u
for (int j=1;j<=n;j++)
{
if ((!s[j])&&(dist[j]
u=j;
mindist=dist[j];
}
}
s[u]=true;//将u点加入s集合
// 更新dist值
for(int j=1;j<=n;j++)//当s集合加入新点的时候需要更新dist[]和prev[]
{
if ((!s[j])&&(c[u][j]
int newdist=dist[u]+c[u][j];//新点到源点的距离+新点到j点的距离
if (newdist
dist[j]=newdist;
prev[j]=u;//新点成了j的前驱点，表示此时从源点到j点经过u距离最短
}
}
}
}
}
//输出最短路径 v源点，i终点，
void Traceback(int v, int i, int prev[])
{
// 源点等于终点时，即找出全部路径
if (v==i)
{
printf("%d",i);
return;
}
Traceback(v,prev[i],prev);
printf("->%d",i);
}
int main()
{
int dist[N+1]; // 从源到顶点i的最短特殊路径长度
int prev[N+1]; // 从源到顶点i的最短路径上前一个顶点
//随机生成带权有向图
int i,j,c[N+1][N+1];
printf("随机生成矩阵:n");
for(i=0;i
for(j=0;j
c[i][j]=rand()%5;
c[0][j]=j;
c[i][0]=i;
if(i==j||c[i][j]==0)
c[i][j]=M;
printf("%d ",c[i][j]);
}
printf("n");
}
//随机指定源点
int v;
printf("请输入指定源点：");
scanf("%d",&v);
// Dijkstra算法
Dijkstra(N,v, dist, prev, c);
for(int i=1; i<=N; i++){
if(dist[i]!=M)
{
printf("源点到顶点%d的最短距离为:%dn",i,dist[i]);
printf("路径为：");
Traceback(v,i, prev);
printf("n");
}
else
printf("源点不能到顶点%dn",i);
}
return 0;
}
五、运行结果
