算法学习笔记（7.7）-贪婪算法（Dijkstra算法-最短路径问题） ...

目次
1.最短路径问题
 2.Dijkstra算法先容
 3.Dijkstra算法演示
4.Dijkstra算法的代码示例

---

1.最短路径问题

   图论中的一个经典问题，通常是指在一个加权图中找到从一个起始顶点到目标顶点的最短路径。
  

• 单源最短路径问题：给定一个加权图和一个起始顶点，要找到从该起始顶点到图中所有其他顶点的最短路径。
  
  
  
  • Dijkstra算法：适用于没有负权边的图，能够找到单源最短路径。
    
  • Bellman-Ford算法：适用于存在负权边的图，能够找到单源最短路径。
    
  
  
• 全源最短路径问题：给定一个加权图，要找到图中恣意两个顶点之间的最短路径。
  
  
  
  • Floyd-Warshall算法：适用于有向图或无向图，能够找到所有顶点之间的最短路径。
    
  
  
• 最短路径问题的应用：
  
  
  
  • 在网络路由中，确定数据包的最佳路径。
    
  • 在地图应用程序中，找到两个地点之间的最短驾驶路径。
    
  • 在交通规划中，优化公交线路或货运路径。
    
  • 在电路设计中，找到电路中信号传输的最短路径。
    
  
  
• 解决最短路径问题的算法：
  
  
  
  • Dijkstra算法：适用于非负权重的图，能够找到单源最短路径。
    
  • Bellman-Ford算法：适用于存在负权重的图，能够找到单源最短路径。
    
  • A*算法：一种开导式搜刮算法，用于探求从起点到目标点的最短路径。
    
  • Bellman-Ford算法：适用于有向图或无向图，能够找到所有顶点之间的最短路径。
    
  
  

   2.Dijkstra算法先容

   1.Dijkstra算法特点：
  迪科斯彻算法使用了广度优先搜刮解决赋权有向图大概无向图的单源最短路径问题，算法终极得到一个最短路径树。该算法常用于路由算法大概作为其他图算法的一个子模块。
  
  2.Dijkstra算法的步骤：
  2.1 初始化：创建一个空的集合用于存储已经找到最短路径的顶点，以及一个数组用于存储从起始顶点到每个顶点的最短距离。将起始顶点的最短距离设置为0，其他顶点的最短距离设置为无穷大。
  2.2 选取起始顶点：将起始顶点参加集合，更新起始顶点到相邻顶点的最短距离。
  2.3 重复步骤：重复以下步骤，直到所有顶点都被参加集合为止：
   2.3.1 从未参加集合的顶点中选取与起始顶点距离最短的顶点参加集合。
   2.3.2 更新该顶点到相邻顶点的最短距离，如果经过该顶点到相邻顶点的距禒小于已知的最短距离，则更新最短距离。
  2.4 终极结果：当所有顶点都被参加集合后，最短路径就被找到了。
  
  3. Dijkstra算法的特点和适用性：
  3.1 Dijkstra算法适用于带权重的有向图或无向图。
3.2 该算法包管找到的路径是最短的，但条件是图中不能有负权重的边。
3.3 时间复杂度取决于详细实现，通常在稠密图上的时间复杂度为O(V^2)，在稀疏图上的时间复杂度为O(E * log V)。
3.4 Dijkstra算法常用于路由算法、网络分析、地图应用等领域。
  
  4. Dijkstra核心算法思想：
  迪杰斯特拉算法主要特点是从起始点开始，采用贪婪算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
   3.Dijkstra算法演示

   1.用一个 dist 数组生存源点到别的各个节点的距离，dist 表现源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state 如果为真，则表现找到了源点到节点 i 的最短距离，state 如果为假，则表现源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。

  2.源点到源点的距离为 0。即dist[1] = 0。

  3.遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state 置为 1。
  

  4.遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist 加上 i -> j 的距离，即 dist[j] > dist + w[j]（w[j] 为 i -> j 的距离） ，则更新 dist[j] = dist + w[j]。

  5.重复 3 4 步骤，直到所有节点的状态都被置为 1。
  

6.此时 dist 数组中，就生存了源点到别的各个节点的最短距离。
  

  4.Dijkstra算法的代码示例

  

1. //c++代码实现
2. #include <iostream>
3. #include <cstring>
4. #include <algorithm>
5. #include <vector>
6. using namespace std;
8. const int N = 510, M = 100010, INF = 0x3f3f3f3f;
10. int h[N], e[M], ne[M], w[M], idx;
11. //h数组用来储存每个边链表的头部
12. //e数组用来存储每条边指向的节点编号
13. //w用来存储每条边的权重
14. //ne数组用来实现邻接表中的链表结构
15. int dist[N]; //state 记录是否找到了源节点到该节点的最短距离
16. bool state[N]; //dist 数组保存源点到其余各个节点的距离
17. int n, m; //图的节点个数和边数
18. int adjMatrix[N][N];  // 邻接矩阵
20. void add(int a, int b, int c)
21. {
22.         e[idx] = b ; //将当前边的目标节点b存储在，e[idx]中
23.         w[idx] = c ; //将该条边的权重存储在，w[idx]中
24.         ne[idx] = h[a] ; //更新ha将之前节点a的第一条边的索引存储在ne数组，使其一直处于更新状态指向最新的一条边
25.         h[a] = idx++ ;       
26. }
28. // 打印邻接表
29. void printAdjList() {
30.     for (int i = 1; i <= n; ++i) {
31.         cout << "Vertex " << i << ":";
32.         for (int j = h[i]; j != -1; j = ne[j]) {
33.             cout << "-> (" << e[j] << ", " << w[j] << ")";
34.         }
35.         cout << endl;
36.     }
37. }
39. // 创建并打印邻接矩阵
40. void printAdjMatrix() {
41.     // 初始化邻接矩阵
42.     for (int i = 1; i <= n; ++i) {
43.         for (int j = 1; j <= n; ++j) {
44.             if (i == j) adjMatrix[i][j] = 0;
45.             else adjMatrix[i][j] = INF;
46.         }
47.     }
48.    
49.     // 填充邻接矩阵
50.     for (int i = 1; i <= n; ++i) {
51.         for (int j = h[i]; j != -1; j = ne[j]) {
52.             int to = e[j];
53.             adjMatrix[i][to] = min(adjMatrix[i][to], w[j]);  // 如果有重边，保留权重最小的一条
54.         }
55.     }
56.    
57.     // 打印邻接矩阵
58.     for (int i = 1; i <= n; ++i) {
59.         for (int j = 1; j <= n; ++j) {
60.             if (adjMatrix[i][j] == INF) cout << "INF ";
61.             else cout << adjMatrix[i][j] << " ";
62.         }
63.         cout << endl;
64.     }
65. }
67. void Dijkstra()
68. {
69.         memset(dist, 0x3f, sizeof(dist)) ; //dist 初始化数组中的元素为最大值
70.         dist[1] = 0 ;
71.         for (int i = 0 ; i < n ; i++)
72.         {
73.                 int t = -1 ;
74.                 for (int j = 1 ; j <= n ; j++)
75.                 {
76.                         //遍历 dist 数组，找到没有确定最短路径的节点
77.                         if (!state[j] && (t == -1 || dist[j] < dist[t]))
78.                         {
79.                                 t = j ;       
80.                         }
81.                 }
82.                 state[t] = 1 ; //将该位置置为访问
83.                        
84.                 for (int j = h[t]; j != -1 ; j = ne[j]) //遍历 t 所有可以到达的节点i
85.                 {
86.                         int i = e[j] ;
87.                         dist[i] = min(dist[i], dist[t] + w[j]) ; //更新dist[j]
88.                 }       
89.                        
90.         }
91. }
93. int main()
94. {
95.         memset(h, -1, sizeof(h)) ;
96.        
97.         cin >> n >> m ;
98.         while (m--)
99.         {
100.                 int a, b, w ;
101.                 cin >> a >> b >> w ;
102.                 add(a, b, w) ;
103.         }
104.         Dijkstra() ;
105.         if (dist[n] != 0x3f3f3f3f)
106.         {
107.                 cout << dist[n] ;
108.         }
109.         else
110.         {
111.                 cout << "-1" ;
112.         }
113.         // 打印邻接表
114.     printAdjList();
115.     // 创建并打印邻接矩阵
116.     printAdjMatrix();
117.         return 0 ;
118. }

复制代码

1. #python代码示例
3. # 简单的Dijkstra算法
4. import heapq
6. def dijkstra(graph, start) :
7.     # 初始化距离字典，将所有节点的距离设置为无穷大
8.     distances = {node : float('inf') for node in graph}
9.     # 源节点到自身的距离设置为0
10.     distances[start] = 0
11.     # 使用优先队列来进行优化，队列中的元素(距离，节点)
12.     priority_queue = [(0,start)]
14.     while priority_queue :
15.         # 弹出队列中最小距离的节点
16.         current_distance, current_node = heapq.heappop(priority_queue)
17.         # 如果弹出的节点距离大于当前记录的距离，则忽略（已找到更短路径）
18.         if current_distance > distances[current_node] :
19.             continue
20.         # 遍历相邻的节点，更新距离
21.         for neighbor, weight in graph[current_node].items() :
22.             distance = current_distance + weight
23.             # 如果通过当前节点到达相邻节点的距离更短，则更新距离字典和最小堆
24.             if distance < distances[neighbor] :
25.                 distances[neighbor] = distance
26.                 heapq.heappush(priority_queue,(distance,neighbor))
27.                 print(f"更新节点: {neighbor} 的最短路径为: {distance}")
28.     return distances
30. graph = {
31. 'A': {'B': 1, 'C': 3},
32. 'B': {'A': 1, 'C': 1, 'D': 4},
33. 'C': {'A': 3, 'B': 2, 'D': 1},
34. 'D': {'B': 4, 'C': 1}
35. }
36. start = 'A'
37. # print(dijkstra(graph, start))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
39. shortest_paths = dijkstra(graph, start)
40. print("\n从节点 {} 到图中其他节点的最短路径:".format(start))
41. for node, distance in shortest_paths.items():
42.     print(f"到节点 {node} 的最短距离是: {distance}")

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。