精华内容
下载资源
问答
  • 迪杰斯特拉算法详解

    2020-07-04 21:59:38
    迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。  它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。 基本思想 &...

    迪杰斯特拉算法介绍

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。 
    它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。


    基本思想

         通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。

         此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

         初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 ... 重复该操作,直到遍历完所有顶点。


    操作步骤

    (1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

    (2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

    (3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

    (4) 重复步骤(2)和(3),直到遍历完所有顶点。

    单纯的看上面的理论可能比较难以理解,下面通过实例来对该算法进行说明。

    迪杰斯特拉算法图解

    以上图G4为例,来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。

    初始状态:S是已计算出最短路径的顶点集合,U是未计算除最短路径的顶点的集合! 
    第1步:将顶点D加入到S中。 
        此时,S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。     注:C(3)表示C到起点D的距离是3。

    第2步:将顶点C加入到S中。 
        上一步操作之后,U中顶点C到起点D的距离最短;因此,将C加入到S中,同时更新U中顶点的距离。以顶点F为例,之前F到D的距离为∞;但是将C加入到S之后,F到D的距离为9=(F,C)+(C,D)。 
        此时,S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。

    第3步:将顶点E加入到S中。 
        上一步操作之后,U中顶点E到起点D的距离最短;因此,将E加入到S中,同时更新U中顶点的距离。还是以顶点F为例,之前F到D的距离为9;但是将E加入到S之后,F到D的距离为6=(F,E)+(E,D)。 
        此时,S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。

    第4步:将顶点F加入到S中。 
        此时,S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

    第5步:将顶点G加入到S中。 
        此时,S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

    第6步:将顶点B加入到S中。 
        此时,S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

    第7步:将顶点A加入到S中。 
        此时,S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

    此时,起点D到各个顶点的最短距离就计算出来了:A(22) B(13) C(3) D(0) E(4) F(6) G(12)

    迪杰斯特拉算法的代码说明

    以"邻接矩阵"为例对迪杰斯特拉算法进行说明,对于"邻接表"实现的图在后面会给出相应的源码。

    1. 基本定义

    复制代码

    1. // 邻接矩阵
    2. typedef struct _graph
    3. {
    4. char vexs[MAX]; // 顶点集合
    5. int vexnum; // 顶点数
    6. int edgnum; // 边数
    7. int matrix[MAX][MAX]; // 邻接矩阵
    8. }Graph, *PGraph;
    9. // 边的结构体
    10. typedef struct _EdgeData
    11. {
    12. char start; // 边的起点
    13. char end; // 边的终点
    14. int weight; // 边的权重
    15. }EData;

    复制代码

    Graph是邻接矩阵对应的结构体。 
    vexs用于保存顶点,vexnum是顶点数,edgnum是边数;matrix则是用于保存矩阵信息的二维数组。例如,matrix[i][j]=1,则表示"顶点i(即vexs[i])"和"顶点j(即vexs[j])"是邻接点;matrix[i][j]=0,则表示它们不是邻接点。 
    EData是邻接矩阵边对应的结构体。

    2. 迪杰斯特拉算法

    复制代码

    1. /*
    2. * Dijkstra最短路径。
    3. * 即,统计图(G)中"顶点vs"到其它各个顶点的最短路径。
    4. *
    5. * 参数说明:
    6. * G -- 图
    7. * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
    8. * prev -- 前驱顶点数组。即,prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中,位于"顶点i"之前的那个顶点。
    9. * dist -- 长度数组。即,dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
    10. */
    11. void dijkstra(Graph G, int vs, int prev[], int dist[])
    12. {
    13. int i,j,k;
    14. int min;
    15. int tmp;
    16. int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
    17. // 初始化
    18. for (i = 0; i < G.vexnum; i++)
    19. {
    20. flag[i] = 0; // 顶点i的最短路径还没获取到。
    21. prev[i] = 0; // 顶点i的前驱顶点为0。
    22. dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    23. }
    24. // 对"顶点vs"自身进行初始化
    25. flag[vs] = 1;
    26. dist[vs] = 0;
    27. // 遍历G.vexnum-1次;每次找出一个顶点的最短路径。
    28. for (i = 1; i < G.vexnum; i++)
    29. {
    30. // 寻找当前最小的路径;
    31. // 即,在未获取最短路径的顶点中,找到离vs最近的顶点(k)。
    32. min = INF;
    33. for (j = 0; j < G.vexnum; j++)
    34. {
    35. if (flag[j]==0 && dist[j]<min)
    36. {
    37. min = dist[j];
    38. k = j;
    39. }
    40. }
    41. // 标记"顶点k"为已经获取到最短路径
    42. flag[k] = 1;
    43. // 修正当前最短路径和前驱顶点
    44. // 即,当已经"顶点k的最短路径"之后,更新"未获取最短路径的顶点的最短路径和前驱顶点"。
    45. for (j = 0; j < G.vexnum; j++)
    46. {
    47. tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
    48. if (flag[j] == 0 && (tmp < dist[j]) )
    49. {
    50. dist[j] = tmp;
    51. prev[j] = k;
    52. }
    53. }
    54. }
    55. // 打印dijkstra最短路径的结果
    56. printf("dijkstra(%c): \n", G.vexs[vs]);
    57. for (i = 0; i < G.vexnum; i++)
    58. printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
    59. }

    复制代码

    迪杰斯特拉算法的源码

    这里分别给出"邻接矩阵图"和"邻接表图"的迪杰斯特拉算法源码。

    1邻接矩阵源码(matrix_udg.c)

    2邻接表源码(list_udg.c)

    展开全文
  • 迪杰斯特拉算法详解+模版+例题

    千次阅读 多人点赞 2020-10-16 20:55:42
    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点...

    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。——百度百科

    基本思想:

    通过Dijkstra计算图G中的最短路径时,需要指定起点vs(即从顶点vs开始计算)。
    此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点,而U则是记录还未求出最短路径的顶点(以及该顶点到起点vs的距离)。
    初始时,S中只有起点vs;U中是除vs之外的顶点,并且U中顶点的路径是"起点vs到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 … 重复该操作,直到遍历完所有顶点。

    操作步骤:

    (1) 初始时,S只包含起点vs;U包含除vs外的其他顶点,且U中顶点的距离为"起点vs到该顶点的距离"[例如,U中顶点v的距离为(vs,v)的长度,然后vs和v不相邻,则v的距离为∞]。

    (2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

    (3) 更新U中各个顶点到起点vs的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(vs,v)的距离可能大于(vs,k)+(k,v)的距离。

    (4) 重复步骤(2)和(3),直到遍历完所有顶点。
    在这里插入图片描述
    上述内容摘自:添加链接描述

    模板:

    int dist[510];//dist[i]存储S到i结点的最短距离
    int book[510];//标记i结点是否访问
    int v[510][510];//存储图信息

    //主要思想一个大循环+两个小循环
    void dijkstra(){
    	int u, minx;
    	book[S] = 1;
    	for(int i = 0; i < N; i++){
    	//dist[]数组初始化,把起始结点S到i结点的距离赋值给diat[i]
    		dist[i] = v[S][i];
    	}
    
    	for(int i = 0; i < N; i++){//大循环
    		minx = INT_MAX;
    		for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径,并记录此结点 
    			if(!book[j] && minx > dist[j]){
    				minx = dist[j];
    				u = j;
    			} 
    		}
    		book[u] = 1;
    		for(int k = 0; k < N; k++){
    		//如果A到B的距离大于A到C的距离加C到B的距离,那么更新数据
    			if(!book[k] && dist[k] > dist[u]+v[u][k]){
    				dist[k] = dist[u]+v[u][k];
    			}
    		}
    	}
    }
    

    例题:

    一、落谷P1339 [USACO09OCT]Heat Wave G
    AC代码:

    #include<stdio.h>
    #include <cstring>
    #include<limits.h>
    #include<iostream>
    using namespace std;
    
    int v[2505][2505];//存储邻接矩阵图 
    int dist[2505];//dist[i]表示到i结点的最短路
    int book[2505];//标记该结点是否访问 
    int n, m, s, t;
    void dijkstra(){
    	//一个大循环套两个小循环 
    	int u, min;
    	book[s] = 1;
    	for(int i = 1; i <= n; i++){
    	//dist数组初始化,把起点到各点的权值赋值给dist 
    		dist[i] = v[s][i];
    	}
    	for(int k = 1; k <= n; k++){//大循环 
    		min = INT_MAX;
    		for(int i = 1; i <= n; i++){
    		//寻找没有被标记并且最小的权值,并记录该结点 
    			if(!book[i] && min > dist[i]){
    				min = dist[i];
    				u = i;
    			}
    		}
    		book[u] = 1;
    		for(int i = 1; i <= n; i++){
    		//更新dist数组,如果A到B的距离大于A到C到B的距离,则更新A到B的最短距离 
    			if(!book[i] && dist[i] > dist[u]+v[u][i]){
    				dist[i] = dist[u]+v[u][i];
    			}
    		}
    	} 
    }
    int main(){
    	scanf("%d %d %d %d", &n, &m, &s, &t);
    	//初始化v数组,最大数
    //	for(int i = 0; i < 2500; i++){
    //		fill(v[i], v[i]+2500, INT_MAX);
    //	} 
    	memset(v, 0x3f, sizeof v);
    	for(int i = 1; i <= m; i++){
    		int u, g, w;
    		scanf("%d %d %d", &u, &g, &w);
    		v[u][g] = v[g][u] = min(v[u][g], w);
    	}
    	dijkstra(); 
    	printf("%d", dist[t]);
    } 
    

    下面代码可输出最短路径所经过的结点(dijkstra + dfs):

    #include<cstdio>
    #include<iostream>
    #include<climits>
    #include<cstring>
    using namespace std;
    
    int N, M, S, D;
    int dist[510];//dist[i]存储S到i结点的最短距离 
    int book[510];//标记i结点是否访问 
    int pre[510];//存储最短路径所经过的结点 
    int v[510][510];//存储图信息 
    
    void dijkstra(){
    	int u, minx;
    	book[S] = 1;
    	for(int i = 0; i < N; i++){
    		dist[i] = v[S][i];
    	}
    
    	for(int i = 0; i < N; i++){
    		minx = INT_MAX;
    		for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径,并记录此结点 
    			if(!book[j] && minx > dist[j]){
    				minx = dist[j];
    				u = j;
    			} 
    		}
    		book[u] = 1;
    		for(int k = 0; k < N; k++){
    			if(!book[k] && dist[k] > dist[u]+v[u][k]){
    				dist[k] = dist[u]+v[u][k];
    				pre[k] = u;
    			} 
    			else if(!book[k] && dist[k] == dist[u]+v[u][k]){
    				pre[k] = u;
    			}
    		}
    	}
    }
    void dfs(int start, int end){
    	if(start == end){
    		printf("%d ", start);
    		return;
    	}
    	dfs(start, pre[end]);
    	printf("%d ", end);
    }
    int main(){
    	scanf("%d %d %d %d", &N, &M, &S, &D);
    	fill(v[0], v[0]+510*510, INT_MAX-1);
    	for(int i = 0; i < M; i++){
    		int a, b, c, d;
    		scanf("%d %d %d", &a, &b, &c);
    		v[a][b] = v[b][a] = min(v[a][b], c);
    	}
    	dijkstra();
    	dfs(S, D);
    	printf("%d", dist[D]);
    	return 0;
    }
    

    二、1030 Travel Plan (30分)——C/C++(dijsktra + DFS)
    AC代码:

    #include<cstdio>
    #include<iostream>
    #include<climits>
    #include<vector>
    using namespace std;
    
    int N, M, S, D;
    int dist[510];//dist[i]存储S到i结点的最短距离 
    int book[510];//标记i结点是否访问 
    int v[510][510];//存储图信息 
    int cost[510][510];//存储花费信息 
    vector <int> pre[510];//存储最短路径所经过的结点 
    vector <int> path, temppath;
    int mincost = INT_MAX;
    
    void dijkstra(){
    	fill(dist, dist+510, INT_MAX-1);
    	int u, minx;
    	pre[S].push_back(S);
    	dist[S] = 0;
    	for(int i = 0; i < N; i++){
    		minx = INT_MAX;
    		for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径,并记录此结点 
    			if(!book[j] && minx > dist[j]){
    				minx = dist[j];
    				u = j;
    			} 
    		}
    		book[u] = 1;
    		for(int k = 0; k < N; k++){
    			if(!book[k] && v[u][k] != INT_MAX){
    				if(dist[k] > dist[u]+v[u][k]){
    					dist[k] = dist[u]+v[u][k];
    					pre[k].clear();
    					pre[k].push_back(u);
    				} 
    				else if(dist[k] == dist[u]+v[u][k]){
    					pre[k].push_back(u);
    				}
    			}
    		}
    	}
    }
    void dfs(int v){
    	temppath.push_back(v);
    	if(S == v){
    		int tempcost = 0;
    		for(int i = temppath.size()-1; i >= 1; i--){
    			int id = temppath[i], id1 = temppath[i-1];
    			tempcost += cost[id][id1];
    		}
    		if(mincost > tempcost){
    			mincost = tempcost;
    			path = temppath;
    		}
    		temppath.pop_back();
    		return;
    	}
    	for(int i = 0; i < pre[v].size(); i++){
    		dfs(pre[v][i]);
    	}
    	temppath.pop_back();
    }
    int main(){
    	scanf("%d %d %d %d", &N, &M, &S, &D);
    	fill(v[0], v[0]+510*510, INT_MAX-1);
    	for(int i = 0; i < M; i++){
    		int a, b, c, d;
    		scanf("%d %d %d %d", &a, &b, &c, &d);
    		v[a][b] = v[b][a] = min(v[a][b], c);
    		cost[a][b] = cost[b][a] = d;
    	}
    	dijkstra();
    	dfs(D);
    	for(int i = path.size()-1; i >= 0; i--){
    		printf("%d ", path[i]);
    	}
    	printf("%d %d", dist[D], mincost);
    	return 0;
    }
    
    

    三、题目连接:洛谷P3317

    AC代码:

    #include<cstdio>
    #include<iostream>
    #include<climits>
    using namespace std;
    struct Edge{
    	int to, w, next;
    }edge[1000010];
    
    int dist[10010];
    int head[10010];
    int book[10010];
    int n, m, s, idx = 1;
    
    void add(int a, int b, int c){
    	edge[idx].to = b;
    	edge[idx].w = c;
    	edge[idx].next = head[a];
    	head[a] = idx++; 
    }
    void dijkstra(){
    	fill(dist, dist + 10010, INT_MAX);
    	dist[s] = 0;
    	int temp = s;
    	while(!book[temp]){
    		book[temp] = 1;
    		for(int i = head[temp]; i != -1; i = edge[i].next){
    			if(!book[edge[i].to] && dist[edge[i].to] > dist[temp] + edge[i].w){
    				dist[edge[i].to] = dist[temp] + edge[i].w;
    			}
    		}
    		int minn = INT_MAX;
    		for(int i = 1; i <= n; i++){
    			if(!book[i] && minn > dist[i]){
    				minn = dist[i];
    				temp = i;
    			}
    		}
    	}
    }
    int main(){
    	fill(head, head + 10010, -1);
    	scanf("%d %d %d", &n, &m, &s);
    	for(int i = 0; i < m; i++){
    		int a, b, c;
    		scanf("%d %d %d", &a, &b, &c);
    		add(a, b, c);
    	}
    	dijkstra();
    	for(int i = 1; i <= n; i++){
    		if(i < n)
    			printf("%d ", dist[i]);
    		else
    			printf("%d", dist[i]);
    	}
    	
    	return 0;
    } 
    
    
    展开全文
  • 基于邻接矩阵的迪杰斯特拉算法实现 #include<bits/stdc++.h> using namespace std; const int MAXV = 1000;//最大的顶数 const int INF = 1000000000;//一个很大的数 int n, G[MAXV][MAXV];//n为顶点数,...

    Dijkstra算法解决的是单源最短路径问题,在给定图和起点的情况下计算到各个结点的最短路径。

    基于邻接矩阵的迪杰斯特拉算法实现

    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXV = 1000;//最大的顶数
    const int INF = 1000000000;//一个很大的数
    
    int n, G[MAXV][MAXV];//n为顶点数,MAXV表示的是最大的结点数
    int d[MAXV];//起点到其他各点的最短路径长度
    int pre[MAXV];//记录每一个最短路径的前驱下标
    bool visit[MAXV] = { false };//表示本结点是否被访问
    
    //首先应该明确的是我们使用迪杰斯特拉算法计算的已知起点的情况下原点到其他点的最小距离    使用d[MAX]表示
    void Dijkstra(int s) {//唯一的参数表示s
    
    	//TODO1: 初始化迪杰斯特拉算法所需要的几个数组:   1.d  2. pre  
    
    	fill(d, d + MAXV, INF);//将起点到各点的长度初始化为INF
    	for (int i = 0; i < n; i++) {//初始化的时候所有的前驱都指向自己
    		pre[i] = i;
    	}
    
    
    	//TODO2:  开始迪杰斯特拉算法的遍历,开始的时候初始化条件是源点到自身的距离为0
    
    	d[s] = 0;//到自身的距离为0
    	for (int i = 0; i < n; i++) {//遍历每一个结点
    		int u = -1, MIN = INF;
    		for (int j = 0; j < n; j++) {//找到当前状态下的最短距离,使用u记录下标
    			if (visit[j] == false && d[j] < MIN) {
    				u = j;
    				MIN = d[j];
    			}
    		}
    		if (u == -1) {//未找到此时的最短路径,剩下的结点和起点都是不连通的
    			return;
    		}
    		visit[u] = true;//表示本节点已经被访问到
    		for (int v = 0; v < n; v++) {//找到了本次需要迭代的对象   u和v可能是相同的
    			//如果v没有访问 并且 u和v之间可达 并且 本次可以通过迭代减小两个点之间的距离
    			if (visit[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
    				d[v] = d[u] + G[u][v];//更新d[v]
    				pre[v] = u;
    			}
    		}
    	}
    }
    int main() {
    	return 0;
    }
    

    例题 1030 Travel Plan

    题目大意

    旅行者的地图给出了高速公路沿线城市之间的距离,以及每条高速公路的成本。现在您应该编写一个程序来帮助旅行者决定他/她的出发城市和目的地之间的最短路径。如果这样的最短路径不是唯一的,则应该输出成本最低的路径,该路径保证唯一。

    代码

    #include<bits/stdc++.h>
    using namespace std;
    
    const int INF = 1000000000;
    const int MAXV = 510;
    
    int n, m, s, d;
    
    
    int minCost = INT_MAX;
    
    int G[MAXV][MAXV];
    int cost[MAXV][MAXV];
    int dis[MAXV];//两点之间的距离
    vector<int> pre[MAXV];//表示前驱
    bool visit[MAXV] = { false };//表示是否已经访问过
    
    vector<int> temPath, path;
    
    void Dijkstra(int s) {//s表示源端
    	//初始化
    	fill(dis, dis + MAXV, INF);//开始的时候每一个点都是不可达到的
    	
    	dis[s] = 0;
    
    	for (int i = 0; i < n; i++) {
    		int u = -1;//表示最短路径的一个点
    		int MIN = INF;
    		for (int j = 0; j < n; j++) {
    			if (visit[j] == false && dis[j] < MIN) {
    				u = j;
    				MIN = dis[j];
    			}
    		}
    		if (u == -1) {
    			//没有在本连通块中找到最小的最短路径
    			return;
    		}
    		else {
    			visit[u] = true;
    			for (int v = 0; v < n; v++) {
    				if (visit[v] == false && G[u][v] != INF) {//没有访问过,可达
    					if (dis[u] + G[u][v] < dis[v]) {//可以更新
    						dis[v] = dis[u] + G[u][v];
    						pre[v].clear();
    						pre[v].push_back(u);
    					}
    					else if (dis[u] + G[u][v] == dis[v]) {
    						pre[v].push_back(u);
    					}
    				}
    			}
    		}
    	}
    }
    
    
    void DFS(int v) {
    	if (v == s) {
    		temPath.push_back(v);
    		int temCost = 0;
    		for (int i = temPath.size() - 1; i > 0; i--) {//倒着访问 计算路径上的总边权
    			int id = temPath[i];
    			int idNext = temPath[i - 1];
    			temCost += cost[id][idNext];
    		}
    		if (minCost > temCost) {
    			minCost = temCost;
    			path = temPath;
    		}
    		temPath.pop_back();
    		return;
    	}
    	temPath.push_back(v);
    	for (int i = 0; i < pre[v].size(); i++) {
    		DFS(pre[v][i]);
    	}
    	temPath.pop_back();
    }
    
    int main() {
    	cin >> n >> m >> s >> d;
    	int c1, c2, di, cos;
    	//初始化图
    	fill(G[0], G[0] + MAXV * MAXV, INF);
    	fill(cost[0], cost[0] + MAXV * MAXV, INF);
    	for (int i = 0; i < m; i++) {
    		cin >> c1 >> c2 >> di >> cos;
    		G[c1][c2] = G[c2][c1] = di;
    		cost[c1][c2] = cost[c2][c1] = cos;
    	}
    
    	Dijkstra(s);//使用迪杰斯特拉算法计算源点的最短距离
    
    	DFS(d);
    
    	for (int i = path.size() - 1; i >= 0; i--) {
    		cout << path[i] << ' ';
    	}
    
    
    	cout << dis[d] << ' ' << minCost << endl;
    
    
    	return 0;
    }
    
    展开全文
  • 前言:相对于暴力简单的Floyd算法,Dijkstra算法更为有用且复杂度较为合理--O(N^2)。今天就为大家介绍一下这个算法。Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个...

    转载文章,原文地址:https://blog.csdn.net/qq_39521554/article/details/79333690
    原文有一处笔误,这里已修改

    前言:



    相对于暴力简单的Floyd算法,Dijkstra算法更为有用且复杂度较为合理--O(N^2)。今天就为大家介绍一下这个算法。Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。


    算法思路:


    Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s

    然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点, 然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。 然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    Dijkstra算法

    090644t797fce7n20of7j9.png


    与Floyd-Warshall算法一样这里仍然使用二维数组e来存储顶点之间边的关系,初始值如下。
    090651l6pt4666tptut66u.png

    我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程,如下。
    090657ofidcactthcig33i.png

    我们将此时dis数组中的值称为最短路的“估计值”。

    Step 1:

           既然是求1号顶点到其余各个顶点的最短路程,那就先找一个离1号顶点最近的顶点。通过数组dis可知当前离1号顶点最近是2号顶点。当选择了2号顶点后,dis[2]的值就已经从“估计值”变为了“确定值”,即1号顶点到2号顶点的最短路程就是当前dis[2]值。为什么呢?你想啊,目前离1号顶点最近的是2号顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得1号顶点到2号顶点的路程进一步缩短了。因为1号顶点到其它顶点的路程肯定没有1号到2号顶点短

    Step 2:

           既然选了2号顶点,接下来再来看2号顶点有哪些出边呢。有2->3和2->4这两条边。先讨论通过2->3这条边能否让1号顶点到3号顶点的路程变短。也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1号顶点到3号顶点的路程。dis[2]+e[2][3]中dis[2]表示1号顶点到2号顶点的路程,e[2][3]表示2->3这条边。所以dis[2]+e[2][3]就表示从1号顶点先到2号顶点,再通过2->3这条边,到达3号顶点的路程。

    Step 3:

           我们发现dis[3]=12,dis[2]+e[2][3]=1+9=10,dis[3]>dis[2]+e[2][3],因此dis[3]要更新为10。这个过程有个专业术语叫做“松弛”。即1号顶点到3号顶点的路程即dis[3],通过2->3这条边松弛成功。这便是Dijkstra算法的主要思想:通过“边”来松弛1号顶点到其余各个顶点的路程。

           同理通过2->4(e[2][4]),可以将dis[4]的值从∞松弛为4(dis[4]初始为∞,dis[2]+e[2][4]=1+3=4,dis[4]>dis[2]+e[2][4],因此dis[4]要更新为4)。

    Step 4:

           刚才我们对2号顶点所有的出边进行了松弛。松弛完毕之后dis数组为:
    090706vmjy7l2ee2lyalia.png

           接下来,继续在剩下的3、4、5和6号顶点中,选出离1号顶点最近的顶点。通过上面更新过dis数组,当前离1号顶点最近是4号顶点。此时,dis[4]的值已经从“估计值”变为了“确定值”。下面继续对4号顶点的所有出边(4->3,4->5和4->6)用刚才的方法进行松弛。松弛完毕之后dis数组为:
    090714f2p1wppynngj2pep.png

           继续在剩下的3、5和6号顶点中,选出离1号顶点最近的顶点,这次选择3号顶点。此时,dis[3]的值已经从“估计值”变为了“确定值”。对3号顶点的所有出边(3->5)进行松弛。松弛完毕之后dis数组为:
    090722ywunackk35i8cni5.png

           继续在剩下的5和6号顶点中,选出离1号顶点最近的顶点,这次选择5号顶点。此时,dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边(5->6)进行松弛。松弛完毕之后dis数组为:
    090730eq6oqzyq7laqha9y.png

           最后对6号顶点所有点出边进行松弛。因为这个例子中6号顶点没有出边,因此不用处理。到此,dis数组中所有的值都已经从“估计值”变为了“确定值”。
           最终dis数组如下,这便是1号顶点到其余各个顶点的最短路径。
    090738azt5clcozl899ekt.png

           现在来总结一下刚才的算法。算法的基本思想是:每次找到离源点(上面例子的源点就是1号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。基本步骤如下:

    • 将所有的顶点分为两部分:已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book[ i ]数组来记录哪些点在集合P中。例如对于某个顶点i,如果book[ i ]为1则表示这个顶点在集合P中,如果book[ i ]为0则表示这个顶点在集合Q中。

    • 设置源点s到自己的最短路径为0即dis=0。若存在源点有能直接到达的顶点i,则把dis[ i ]设为e[s][ i ]。同时把所有其它(源点不能直接到达的)顶点的最短路径为设为∞。

    • 在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边,对每一条边进行松弛操作。例如存在一条从u到v的边,那么可以通过将边u->v添加到尾部来拓展一条从s到v的路径,这条路径的长度是dis[u]+e[u][v]。如果这个值比目前已知的dis[v]的值要小,我们可以用新值来替代当前dis[v]中的值。

    • 重复第3步,如果集合Q为空,算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

    参考文章:http://blog.51cto.com/ahalei/1387799

    展开全文
  • //当当当~~~~ 重点来了 , 迪杰斯特拉算法核心语句 for(int i = 1 ; i ; i++)//循环dis数组 , 找最近的点 { min = INF; for(int j = 1 ; j ; j++)// { if(book[j] == 0 && dis[j] ) { min = dis...
  • dijkstra算法详解迪杰斯特拉算法)简单易懂

    千次阅读 多人点赞 2020-07-29 09:12:01
    dijkstra算法详解迪杰斯特拉算法)~~简单易懂 PS:此算法不能用于求负权图,要求所有边的权重都为非负值。 一、简介(百度百科) 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又...
  • 迪杰斯特拉这是一个按路径长度递增次序产生最短路径的算法。具体代码如下: /*1*/import java.util.Scanner; /*2*/class Graph{ /*3*/ int[][] edge; //图的邻接矩阵 /*4*/ int numPoint; //图中顶点数目 ...
  • 详解最短路径中的迪杰斯特拉算法 0x01.关于迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 201
精华内容 80
关键字:

迪杰斯特拉算法详解