对图论有一定了解的人,一定知道最短路。
最短路算法一共有4中,严格来说是3种,应为最后一个是第3个的优化。
他们分别是:
Floyd、Dijkstra、Bellman-Ford和SPFA算法
Floyd是最暴力的思想,这里就不在阐述。
今天,我们来讲Dijkstra算法,中文名迪杰斯特拉。
Dijkstra是单源最短路,也就是计算从一点出发,到各个点的距离。
这是一个类似贪心的算法,是否流程如下:
1.初始化dist [ v0 ] = 0;(v0是源点),其余dist为INF(正无穷,通常用0x3f3f3f3f表示)
2.找出未标记的、dist [ x ] 的最小 x ,标记 x;
3.扫描节点x的所有 出边 (x,y,z)表示x到y有权值为z的边。,若dist [ y ] > dist [ x ] + z,则使用 dist [ x ] + z 更新 dist [ y ];
4.重复2~3,直到所有点都被标记。
dist [ x ] 就是 v0 到 x 的最短路径。
代码实现:
1 int a[3010][3010]/*图*/,d[3010],n,m; 2 bool v[3010];//是否被访问 3 void dijkstra(int v0)//源点 4 { 5 memset(d,0x3f3f3f3f,sizeof(d));//距离 6 memset(v,0,sizeof(v));//初始化都未访问 7 d[v0]=0; 8 for(int i=1;i<n;i++)//重复n-1次 9 { 10 int x=0; 11 //找到未标记的dist最小的节点 12 for(int j=1;j<=n;j++) 13 if(!v[j]&&(x==0||d[j]<d[x]))//j为访问或dist[j]<dist[x]; 14 x=j; 15 v[x]=1; 16 //用x更新其他点 17 for(int y=1;y<=n;y++) 18 d[y]=min(d[y],d[x]+a[x][y]/*x到y的边权值*/); 19 } 20 }
这就是模板of Dijkstra,很好理解,大家要是有不理解的,也可以查相关资料,去了解更多的知识。