• Dijkstra算法基础详解，附有练习题

    介绍

    Dijkstra算法是一种用于求解单源最短路径问题的经典算法。它可以在给定有向加权图（无向是特殊的有向）中，从一个起点到其他所有节点的最短路径。

    作用：

    在给定的加权图中，求一个点到其余点的最短路径

    基本思想：

    • 初始化一个距离数组dist[]，表示起点到各个节点的当前最短距离，初始时起点的最短距离为0，其余节点的最短距离为无穷大。
    • 创建一个集合S，用于存放已经确定最短路径的节点，初始时集合S为空。
    • 重复以下步骤，直到集合S包含了所有节点：
      • 在未确定最短路径的节点中，选择一个节点v，选择的是dist[v]值最小，将该节点加入集合S。
      • 更新节点v的所有邻接节点u的最短距离，如果通过节点v到达节点u的距离比当前最短路径更短，则更新最短距离dist[u]为新的最短距离。
      • 表示为： dist[u] = min(dist[u],dist[v]+edge[v][u])

    Dijkstra算法的关键是如何选择节点v，这里使用了贪心策略，每次选择距离起点最近的未确定最短路径的节点，确保每次加入的节点都是当前最短距离确定的。

    朴素模板如下：

    1. int dijkstra(int b)//求b到各个点的距离
    2. {
    3. 	memset(dist, 0x3f, sizeof dist);
    4. 	dist[b] = 0;
    5.  
    6. 	for (int i = 0; i < n - 1; i++)
    7. 	{
    8. 		int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
    9. 		for (int j = 1; j <= n; j++)
    10. 			if (!st[j] && (t == -1 || dist[t] > dist[j]))
    11. 				t = j;
    12.  
    13. 		//从t这个点更新到其他点的距离。
    14. 		//虽然是遍历了每个点，但并不代表t可以到任意点，
    15. 		//因为会把到不了的边的距离设为inf，就避免了考虑t点可以到哪些点的问题
    16. 		for (int j = 1; j <= n; j++)
    17. 			dist[j] = min(dist[j], dist[t] + v[t][j]);
    18.  
    19. 		st[t] = true;
    20. 	}
    21.  
    22. 	if (dist[n] == 0x3f3f3f3f) return -1;
    23. 	return dist[n];
    24. }

    堆优化版

    可以看到，朴素版有一个遍历找dist最小的操作，如果用小根堆维护dist的话，就可以一下子找到最小了，无需遍历

    插入优先队列的知识点

    可以使用标准库中的priority_queue来实现小根堆和大根堆。priority_queue默认实现的是大根堆，如果需要实现小根堆，可以通过自定义比较器来改变默认行为。

    priority_queue, greater> minHeap;

    1. int dijkstra(int b)//求b到各个点的距离
    2. {
    3. 	memset(dist, 0x3f, sizeof dist);
    4. 	dist[b] = 0;
    5.  
    6. 	
    7.     priority_queue, cmp> q;
    8. 	q.push({ b,0 });
    9. 	
    10. 	while (q.size()) {
    11. 		node t = q.top();
    12. 		q.pop();
    13. 		int ver = t.v, distance = t.w;
    14. 		//此时dist[ver] == distance，是最小的
    15. 		if (st[ver]) continue;
    16.  
    17. 		st[ver] = true;
    18. 		for (int i = 0; i < edge[ver].size();i++) {
    19. 			//更新ver可以到达的点
    20. 			if (dist[i] > edge[ver][i] + distance) {
    21. 				dist[i] = edge[ver][i] + distance;
    22. 				q.push({ i,dist[i] });
    23. 			}
    24. 		}
    25.  
    26. 	}
    27.  
    28.  
    29.  
    30.  
    31. 	if (dist[n] == 0x3f3f3f3f) return -1;
    32. 	return dist[n];
    33. }

    邻接表写法

    Dijkstra求最短路 II

    1. const int N = 150010;
    2. typedef pair<int,int> PII;
    3.  
    4. int h[N],w[N],ne[N],e[N],idx;
    5. void add(int u,int v,int we){
    6.     w[idx] = we,ne[idx] = h[u],e[idx] = v;
    7.     h[u] = idx++;
    8. }
    9. int dist[N];bool st[N];
    10. int n,m;
    11. int dijkstra(int b){
    12.     memset(dist,0x3f,sizeof dist);
    13.     dist[b] = 0;
    14.     
    15.     //PII的第一个元素是点x到b点的距离，第二个元素是点x
    16.     priority_queue,greater> heap;
    17.     heap.push({0,b});
    18.     while(heap.size()){
    19.         auto t = heap.top();
    20.         heap.pop();
    21.         
    22.         int ver = t.second,distance = t.first;
    23.         if(st[ver]) continue;
    24.         st[ver] = true;
    25.         //访问ver能到达的点，更新ver到这些点的距离
    26.         for(int i = h[ver];i!=-1;i = ne[i]){
    27.             //切记了，i只是编号！
    28.             int j = e[i];//j才是ver能到达的点
    29.             if(dist[j] > distance + w[i]){
    30.                 dist[j] = distance + w[i];
    31.                 heap.push({dist[j],j});
    32.             }
    33.             
    34.         }
    35.         
    36.     }
    37.     if(dist[n] == 0x3f3f3f3f) return -1;
    38.     else return dist[n];
    39.     
    40. }
    41. void solve() {
    42. 	cin>>n>>m;
    43. 	memset(h,-1,sizeof h);
    44. 	//memset(st,false,sizeof st);
    45. 	//idx = 1;
    46. 	while(m--){
    47. 	    int a,b,c;cin>>a>>b>>c;
    48. 	    add(a,b,c);
    49. 	}
    50. 	int t = dijkstra(1);
    51. 	cout<
    52. 	
    53. }

    Dijkstra序列

    输入样例：
    1. 5 7
    2. 1 2 2
    3. 1 5 1
    4. 2 3 1
    5. 2 4 1
    6. 2 5 2
    7. 3 5 1
    8. 3 4 1
    9. 4
    10. 5 1 3 4 2
    11. 5 3 1 2 4
    12. 2 3 4 5 1
    13. 3 2 1 5 4
    输出样例：
    1. Yes
    2. Yes
    3. Yes
    4. No

    分析：还是要先弄目标dijkstra序列的含义是什么，这个困扰我了很久。

    我们知道，在构建dist数组时，每次是选 还没有选过 且 当前dist最小 的点，在这个点的基础上进行更新。然后要选n次，我们这n次选的点的序列就称作dijkstra序列（第一个点就是起点）。

    例如：5，1，3，4，2。代表点5是起点，然后选点1，点3，点4，点2。

    设每次选的点为dist[i]，那么dist[i]一定小于当前所有还没选过的点。以这个为判断条件，如果不满足，则不是一个dijkstra序列。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include 
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. #include 
    17. #include
    18. #include 
    19.  
    20. #define inf 0x3f3f3f3f
    21. #define int long long
    22. const int N =1010;
    23. //#include 
    24. typedef long long ll;
    25. #include
    26. using namespace std;
    27.  
    28. //long long MAX(long long a, long long b) { return a < b ? b : a; }
    29.  
    30. int n, m;
    31.  
    32.  
    33. int v[N][N];//存每条边,v[i][j]代表i到j的距离。如果i到j没有直接的路径，那么设为inf
    34. int dist[N];//存i号点到各个点的最短距离
    35. int st[N];//存到达该点该点是否已经确定最短路径
    36. int q[N];
    37.  
    38. int dijkstra() {//从b开始，到各个点的距离
    39. 	memset(dist, inf, sizeof(dist));
    40. 	memset(st, 0, sizeof(st));
    41. 	dist[q[0]] = 0;//到达自己的距离是0
    42.  
    43. 	
    44. 	for (int i = 0; i < n; i++) {
    45.  
    46. 		int cur = q[i];
    47. 		for (int j = 1; j <= n; j++) {
    48. 			if (!st[j] && dist[j]
    49. 				return false;
    50. 			}
    51. 		}
    52.  
    53. 		//从cur这个点更新到其他点的距离。
    54. 		//虽然是遍历了每个点，但并不代表cur可以到任意点，
    55. 		//因为会把到不了的边的距离设为inf，就避免了考虑cur点可以到哪些点的问题
    56. 		for (int j = 1; j <= n; j++) {
    57. 			dist[j] = min(dist[j], dist[cur] + v[cur][j]);
    58. 		}
    59.  
    60. 		st[cur] = 1;
    61. 	}
    62.  
    63. 	return 1;
    64. }
    65. signed main() {
    66. 	cin >> n >> m;
    67. 	memset(v, inf, sizeof(v));
    68.  
    69. 	for (int i = 0; i < m; i++) {
    70. 		int a, b, d; cin >> a >> b >> d;
    71.  
    72. 		//因为是无向图
    73. 		v[a][b] = d;
    74. 		v[b][a] = d;
    75. 	}
    76. 	int k; cin >> k;
    77. 	while (k--) {
    78. 		vector<int> t;
    79. 		t.push_back(0);
    80. 		for (int i = 0; i < n; i++) {
    81. 			cin >> q[i];
    82. 		}
    83. 		if (dijkstra()) cout << "Yes" << endl;
    84. 		else cout << "No" << endl;
    85.  
    86. 	}
    87.  
    88. 	return 0;
    89. }

    奶牛回家

    输入样例：
    1. 5
    2. A d 6
    3. B d 3
    4. C e 9
    5. d Z 8
    6. e Z 3
    输出样例：
    B 11

    分析：简单题。命名为大写字母的牧场才有牛，可以逆向思考，从牛棚Z开始往这些牧场走，那条路最短。

    易错点，两个牧场间可能有多条路，这些路长度可能不一样，注意判断。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include 
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include 
    16. #include
    17. #include 
    18.  
    19. #define inf 0x3f3f3f3f
    20. #define int long long
    21. const int N =1010;
    22. //#include 
    23. typedef long long ll;
    24. #include
    25. using namespace std;
    26.  
    27. //long long MAX(long long a, long long b) { return a < b ? b : a; }
    28.  
    29. int n;
    30.  
    31. int v[N][N];  // 存储每条边
    32. int dist[N];  // 存储1号点到每个点的最短距离
    33. bool st[N];   // 存储每个点的最短路是否已经确定
    34.  
    35. int get(char x) {
    36. 	if (x >= 'A' && x <= 'Z') return x - 'A' + 1;
    37. 	return x - 'a' + 26 + 1;
    38.  
    39. }
    40. void dijkstra() {
    41. 	memset(dist, inf, sizeof(dist));
    42. 	memset(st, 0, sizeof(st));
    43. 	dist[26] = 0;//Z到Z距离是0
    44. 	for (int i = 1; i <= 52; i++) {
    45. 		int cur = -1;
    46. 		for (int j = 1; j <= 52; j++) {
    47. 			if (!st[j] && (cur == -1 || dist[cur] > dist[j])) {
    48. 				cur = j;
    49. 			}
    50. 		}
    51.  
    52. 		for (int j = 1; j <= 52; j++) {
    53. 			dist[j] = min(dist[j], dist[cur] + v[cur][j]);
    54. 		}
    55. 		st[cur] = 1;
    56. 	}
    57.  
    58. }
    59. signed main() {
    60. 	cin >> n;
    61. 	memset(v, inf, sizeof(v));
    62. 	while (n--) {
    63. 		char a, b; int c;
    64. 		cin >> a >> b >> c;
    65. 		int d = get(a);
    66. 		int e = get(b);
    67. 		v[d][e] = v[e][d] = min(v[d][e], c);
    68.  
    69. 	}
    70. 	dijkstra();
    71. 	int index = 0, len = inf;
    72. 	for (int i = 1; i <= 25; i++) {
    73. 		if (len > dist[i] && dist[i] <= 10000 * 1000) {
    74.                            //如果大于这个距离就是没有到i的路，距离为inf
    75. 			len = dist[i];
    76. 			index = i;
    77. 		}
    78. 	}
    79. 	printf("%c %lld", index + 'A' - 1, len);
    80.  
    81. 	return 0;
    82. }

  • 相关阅读:
    CLR via C#-托管堆和垃圾回收
    架构核心技术之分布式消息队列
    Kafka副本选举流程
    java 小练习
    Java21 + SpringBoot3使用Spring Security时如何在子线程中获取到认证信息
    B. The Walkway Codeforces Round 893 (Div. 2)
    前端不安装Nginx情况下部署
    Android多线程学习：线程池（二）
    开源国内镜像站 操作系统、中间件、开发环境
    【后端框架】MyBatis（1）
  • 原文地址：https://blog.csdn.net/clmm_/article/details/133961313