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++; } }