给定带权有向图，其中每条边的权是非负实数。
给定V中的一个顶点，称为源，现在要计算从源到所有其他各顶点的最短长度，这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题（Single-Source Shortest Paths）
如图，计算源点v1到其他各个顶点的最短距离，并输出相应的路径。
带权有向图G
输入
第一行 有两个数据n和m，其中n表示结点个数，m表示路径数目；
接下来有m行，每行有三个数据 s, t ,edge ,其中 s 表示路径的起点，t表示路径的终点，edge表示该路径的长度。
当输入n = 0, m = 0 时，输入数据结束。
输出
源点到所有其他各顶点的最短路长度。
输入输出样例
解析：
算法分析(核心)
Dijkstra算法是解单源最短路径问题的一个贪心算法。
基本思想：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
- 初始时，
S中仅含有源。 - 设
u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。 - Dijkstra算法每次从V—S中取出具有最短特殊路长度的顶点
u，将u添加到S中，同时对数组dist作必要的修改。 - 一旦S包含了所有V中顶点，
dist就记录了从源到所有其它顶点之间的最短路径长度。
主函数初始化
顶点个数n，源点v，有向图的邻接矩阵为 c ；
数组 dist保存从源点 v 到每个顶点的最短特殊路径长度
数组 prev保存每个顶点在最短特殊路径上的前一个结点
memset 初始化函数(https://baike.baidu.com/item/memset/4747579?fr=aladdin)
int m,n;
while(scanf("%d%d",&n,&m)!=EOF && (m || n))
{
int i,j;
int dist[NUM] = {0};
int prev[NUM] = {0};
int c[NUM][NUM];
memset(c,1,sizeof(c));
int v,w,edge;
for(i=0; i<m; i++)
{
scanf("%d%d%d",&v,&w,&edge);
c[v][w] = edge;
}
// c[][]接收数据后：
/*
16843009 10 16843009 25 80
16843009 16843009 40 16843009 16843009
16843009 16843009 16843009 16843009 10
16843009 16843009 20 16843009 50
16843009 16843009 16843009 16843009 16843009
*/
dijkstra(n,1,dist,prev,c);
有向图的邻接矩阵
dijkstra算法
#define NUM 100
#define maxint 10000
void dijkstra(int n,int v,int dist[],int prev[],int c[][NUM])
{
int i,j;
bool s[NUM]; //集合S
//初始化数组
for(i=1; i<=n; i++)
{
dist[i] = c[v][i];
s[i] = false;
if (dist[i]>maxint) prev[i] = 0;
else prev[i] = v;
}
初始化后各数组情况：
//初始化源结点
dist[v] = 0;
s[v] = true;
初始化源结点
//其余顶点n-1个
for(i=1; i<n; i++)//循环n-1次
{
//在数组dist中寻找未处理结点的最小值
int mintmp = maxint;
int u = v;
for(j=2; j<=n; j++){
if(!(s[j]) && (dist[j]<mintmp)){
u = j;
mintmp = dist[j];
}
}
//此时找到dist中最小值的结点 u
s[u] = true;//结点u加入s中
//设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
//利用结点更新数组dist
for(j=2; j<=n; j++){
if(!(s[j]) && c[u][j]<maxint){
//newdist为从源点到该点的最短特殊路径
int newdist = dist[u]+c[u][j];
if (newdist<dist[j]){
//修正最短距离
dist[j] = newdist;
//记录j的前一个结点
prev[j] = u;
}
}
}
}
}
未完待续。。。。。。
网友评论