Dijkstra 算法总结
Dijkstra算法思想：
Dijkstra算法又称单源最短路，求一个点到图中其它点的最短路。
假设有两个集合 S 和 T ，S中只包含源点，T中包含除源点外的其它点，开始寻找由源点出发到 T 中点的距离最小的点，让它加入 S 中，然后以加入的点为中间点更新 T 中点到源点的距离（如果源点到中间点的距离加上中间点到 T 中与中间点有关系的点的距离小于源点到有关系的点的距离，就更新有关系的点到源点的距离）然后继续在 T 中寻找到 S 中距离最短的点，重复上述操作，一直找完所有点。
如图：
(1)开始时，s1={v0},s2={v1,v2,v3,v4}，v0到各点的最短路径是{0,10,&,30,100};
(2)在还未进入s1的顶点之中，最短路径为v1，因此s1={v0,v1},由于v1到v2有路径，因此v0到各点的最短路径更新为{0,10,60,30,100};
(3)在还未进入s1的顶点之中，最短路径为v3，因此s1={v0,v1,v3},由于v3到v2、v4有路径，因此v0到各点的最短路径更新为{0,10,50,30,90}；
(4)在还未进入s1的顶点之中，最短路径为v2，因此s1={v0,v1,v3,v2},由于v2到v4有路径，因此v0到各点的最短路径更新为{0,10,50,30,60};
数据结构：
(1)用一个二维数组a[i..j,i..j]来存储各点之间的距离，10000表示无通路：
(2)用数组dist[i..j]表示最短路径；
(3)用集合s表示找到最短路径的结点
代码（模版）：
-
memset(vis,0,sizeof(vis));
-
for(i=1;i<n;i++)
-
d[i]=INF;//赋值无穷大
-
d[0]=0;//源点为零
-
for(i=0;i<n;i++)
-
{
-
int x,min=INF;
-
for(j=0;j<n;j++)
-
if(!vis[j]&&d[j]<=m)
-
min=d[x=j];
-
vis[x]=1;//选中后标记
-
for(k=0;k<n;k++)
-
if(d[k]>d[x]+w[x][k])
-
{
-
d[k]=d[x]+w[x][k];
-
father[k]=x;//记录父亲节点，用于回路打印
-
}
-
}
回路打印：
-
void find(int x)
-
{
-
if(father[x]!=x)
-
{
-
find(father[x]);
-
printf("~~>%d",x);
-
}
-
else
-
printf("%d",x);
-
}
Dijkstra 算法优化：
当图中的边很少时用邻接矩阵存就会浪费空间，也就是说当图为稀疏图时可以用邻接表存图。
首先给每条边编号，然后用first[ u ]保存结点 u 的第一条边的编号，next[ e ]表示编号为 e 的边的“ 下一条边 ”的编号。
代码（有向图）：
-
int n,m;//有向图
-
int first[MAX];//first[]下标为图中点的标号，里面存的是边的序号
-
int u[MAX],v[MAX],w[MAX],next[MAX];//next[]下标为边的序号，里面存的也是边的序号，
-
void read()
-
{
-
scanf("%d%d",&n,&m);
-
for(int i=0;i<n;++i)
-
first[i]=-1;
-
for(int e=0;e<m;++e)//e为每条边的编号
-
{
-
scanf("%d%d%d",&u[e],&v[e],&w[e]);
-
next[e]=first[u[e]];
-
first[u[e]]=e;
-
}
-
}//先找first[]中存的边，然后依据first[]中存的边作为next[]的下标找到next[]中与之相关的边，一直找到next[]=-1，说明找完了
代码（无向图）：
-
int n,m;//无向图
-
int first[MAX];
-
int u[MAX],v[MAX],w[MAX],next[MAX];
-
void read()
-
{
-
scanf("%d%d",&n,&m);
-
for(int i=0;i<n;++i)
-
first[i]=-1;
-
for(int e=0;e<m;++e)
-
{
-
scanf("%d%d%d",&u[e],&v[e],&w[e]);
-
next[e]=first[u[e]];
-
first[u[e]]=e;
-
i++;
-
int t;
-
t=v[i-1];v[i]=u[i-1];u[i]=t;
-
w[i]=w[i-1];
-
next[i]=first[u[i]];
-
first[u[i]]=i;
-
m++;
-
}
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/9469369
- 点赞
- 收藏
- 关注作者
评论（0）