Djkstra求解无向图单源最短路径
图论中有很多很经典的问题和算法思想,如最小生成树,DFS,BFS,Powell染色问题等等。最短路径问题也是其中的经典问题之一,在地图导航等领域非常常用。求解最短路径的常用算法有Dijkstra算法、Floyd算法等等。前者只能求解单源最短路径,后者可以求解任意源到任一点的最短路径,后者的复杂度要比前者高。
在这里具体阐述一下Dijkstra算法求解单源最短路径的基本算法思想:
首先需要做的是创建一个空集S,表示已经遍历过的节点的集合。
选定好源点O之后,便要把源点O放入集合S中。之后进行如下步骤:
1) 如果!S不为空,选择距离源最小的点,称为点V,放入集合S中。
2) 对V的所有后继(针对无向图则为所有相连的节点)进行遍历,当V到某一后继U的距离加上V到源点O的距离要小于从源点O到U的直接距离时,更新源点O到U的距离为OV距离+VU距离。
3)重复进行前两步,直到!S为空为止。
举例:
如下面的一张图,求解点1到其他所有点的最短路径:

讯享网
我们首先先把与点1相连的所有点的距离加进去。以数组dist[i]记录。
首先dist[0] = 0 , dist[1] = 10, dist[2] = INF, dist[3] = 30, dist[4] = 100;
用数组mark[i]表示第i-1个节点是否进入了集合S。
mark[0] = true;
接下来选择距离源最近并且还没有进入S的点。点2。
那么 mark[0] = true; mark[1] = true;
接着,dist [1] + edge[1][2] = 10 + 50 = 60 < dist[2] = INF.
也就是说点1到点2的距离加上点2到点3的距离小于点1到点3的距离(因为他们不相连)。
dist[0] = 0 , dist[1] = 10, dist[2] = 60, dist[3] = 30, dist[4] = 100;
接下来选择距离源最近并且还没有进入S的点。点4。
那么 mark[0] = true; mark[1] = true; mark[3] = true;
接着,dist[3] + edge[3][2] = 30 + 20 = 50 < dist[2] = 60
也就是说点1到点4的距离加上点4到点3的距离小于点1到点3的距离。
dist[0] = 0 , dist[1] = 10, dist[2] = 50, dist[3] = 30, dist[4] = 100;

接着,dist[3] + edge[3][4] = 30 + 60 = 90 < dist[4] = 100
也就是说点1到点4的距离加上点4到点5的距离小于点1到点5的距离。
dist[0] = 0 , dist[1] = 10, dist[2] = 50, dist[3] = 30, dist[4] = 90;
至此,点4的所有后继搜寻完毕。
接下来选择距离源最近并且还没有进入S的点。点3。
那么 mark[0] = true; mark[1] = true; mark[2] = true; mark[3] = true;
接着,dist[2] + edge[2][5] = 50 + 10 = 60 < dist[4] = 90
也就是说点1到点3的距离加上点3到点5的距离小于点1到点5的距离。
dist[0] = 0 , dist[1] = 10, dist[2] = 50, dist[3] = 30, dist[4] = 60;
点3的其余后继不用更新,因为相加的大小都比之前的距离长,不能更新。
最后点5也同上,没有可以更新的距离,至此,所有的点都进入了集合S。
最终点1到其他所有点的最短距离为:
dist[0] = 0
dist[1] = 10
dist[2] = 50
dist[3] = 30
dist[4] = 60
算法思想和举例大致如上,下面给出C++实现代码:
// program : dijkstra algorithm 迪杰斯特拉算法 // author : William.L // version : v1.0 /* 贪心算法,以一个点定为起点,寻找距离源距离最小值的点 按照这个顺序每个点遍历一次。 通过这个点继续往下扩展,寻找到达所有点的最小值。 迪杰斯特拉算法的时间复杂度取决于最小值点的选取,在这里运用了数组而没有建堆,所以时间复杂度为O(n^2) */ #include <iostream> #include <fstream> #include <ctime> #define INF 0xffffff using namespace std; int edge[1000][1000]; int find_min(int size, int* dist, bool* mark){
//这个函数用来选取距离源最近的点。 int min,minp; min = INF; for (int i = 0; i < size; ++i){
if (dist[i] < min && mark[i] == false){
minp = i; min = dist[i]; } } if (min == INF){
for (int i = 0;i < size; ++i){
if (mark[i] == false){
return i; } } } return minp; } bool all_marked(bool* mark, int size){
//判断是否所有点都遍历。 for (int i = 0; i < size; ++i){
if (mark[i] == false){
return false; } } return true; } void dijkstra(int size, int src, int* dist, bool* mark){
dist[src] = 0; mark[src] = true; for (int i = 0;i < size; ++i){
dist[i] = edge[src][i]; } while(1){
if (all_marked(mark,size)){
return; } int u = find_min(size,dist,mark); mark[u] = true; for (int i = 0; i < size; ++i){
if ( dist[u] + edge[u][i] < dist[i] ){
dist[i] = dist[u] + edge[u][i]; } } } } int main(){
int size,src; cin >> size >> src; src--; int edges; cin >> edges; for (int i = 0;i < size; ++i){
for (int j = 0; j < size; ++j){
if (i == j){
edge[i][j] = 0; } else{
edge[i][j] = INF; } } } int v1,v2,len; for(int i = 0;i < edges; ++i){
cin >> v1 >>v2 >> len; edge[v1-1][v2-1] = edge[v2-1][v1-1] = len; //这里是针对无向图,如果是有向图,就不要把对称的位置也赋值。 } bool mark[size]; int dist[size]; dijkstra(size,src,dist,mark); for (int i = 0; i < size; ++i){
cout << "The distance between p" << src+1 << " to p" << i+1 << " is:"; if (dist[i] == INF){
cout << "Infinity!"; } else{
cout << dist[i]; } cout << endl; } return 0; }
讯享网
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80312.html