Dijkstra算法

本文主要是介绍Dijkstra算法 | 迪杰斯特拉算法-迷宫解算器可视化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

该算法维护一组已访问的顶点和一组未访问的顶点。它从源顶点开始，迭代地选择距源具有最小暂定距离的未访问顶点。然后，它访问该顶点的邻居，如果找到更短的路径，则更新它们的暂定距离。这个过程一直持续到到达目的地顶点，或者所有可到达的顶点都被访问过。

在许多应用中都需要 Dijkstra 算法，其中找到两点之间的最短路径至关重要。例如，它可以用于计算机网络的路由协议，也可以用于地图系统来查找起点和目的地之间的最短路径。

Dijkstra 算法可以适用于有向图和无向图，因为该算法被设计为适用于任何类型的图，只要它满足具有非负边权重和连通性的要求。

在有向图中，每条边都有一个方向，表示边所连接的顶点之间的行进方向。在这种情况下，算法在搜索最短路径时遵循边缘的方向。
在无向图中，边没有方向，算法在搜索最短路径时可以沿着边向前和向后遍历。

算法过程

将当前距离标记为 0 的源节点，将其余节点标记为无穷大。
将当前距离最小的未访问节点设置为当前节点。
对于每个邻居，当前节点的N加上相邻节点的当前距离以及连接0->1的边的权重。如果小于Node当前距离，则将其设置为新的N当前距离。
将当前节点 1 标记为已访问。
如果还有未访问的节点，则转步骤2。

实现方式

实现 Dijkstra 算法的方法有多种，但最常见的是：

优先级队列（基于堆的实现）
基于数组的实现

代码实现

Python:

import heapqclass Node:def __init__(self, v, distance):self.v = vself.distance = distancedef __lt__(self, other):return self.distance < other.distancedef dijkstra(V, adj, S):visited = [False] * Vmap = {}q = []map[S] = Node(S, 0)heapq.heappush(q, Node(S, 0))while q:n = heapq.heappop(q)v = n.vdistance = n.distancevisited[v] = TrueadjList = adj[v]for adjLink in adjList:if not visited[adjLink[0]]:if adjLink[0] not in map:map[adjLink[0]] = Node(v, distance + adjLink[1])else:sn = map[adjLink[0]]if distance + adjLink[1] < sn.distance:sn.v = vsn.distance = distance + adjLink[1]heapq.heappush(q, Node(adjLink[0], distance + adjLink[1]))result = [0] * Vfor i in range(V):result[i] = map[i].distancereturn resultdef main():adj = [[] for _ in range(6)]V = 6E = 5u = [0, 0, 1, 2, 4]v = [3, 5, 4, 5, 5]w = [9, 4, 4, 10, 3]for i in range(E):edge = [v[i], w[i]]adj[u[i]].append(edge)edge2 = [u[i], w[i]]adj[v[i]].append(edge2)S = 1result = dijkstra(V, adj, S)print(result)if __name__ == "__main__":main()

C++:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3ftypedef pair<int, int> iPair;class Graph {int V; // No. of verticeslist<pair<int, int> >* adj;public:Graph(int V); // Constructorvoid addEdge(int u, int v, int w);void shortestPath(int s);
};Graph::Graph(int V)
{this->V = V;adj = new list<iPair>[V];
}void Graph::addEdge(int u, int v, int w)
{adj[u].push_back(make_pair(v, w));adj[v].push_back(make_pair(u, w));
}void Graph::shortestPath(int src)
{priority_queue<iPair, vector<iPair>, greater<iPair> >pq;vector<int> dist(V, INF);pq.push(make_pair(0, src));dist[src] = 0;while (!pq.empty()) {int u = pq.top().second;pq.pop();list<pair<int, int> >::iterator i;for (i = adj[u].begin(); i != adj[u].end(); ++i) {int v = (*i).first;int weight = (*i).second;if (dist[v] > dist[u] + weight) {dist[v] = dist[u] + weight;pq.push(make_pair(dist[v], v));}}}printf("Vertex Distance from Source\n");for (int i = 0; i < V; ++i)printf("%d \t\t %d\n", i, dist[i]);
}int main()
{int V = 7;Graph g(V);g.addEdge(0, 1, 2);g.addEdge(0, 2, 6);g.addEdge(1, 3, 5);g.addEdge(2, 3, 8);g.addEdge(3, 4, 10);g.addEdge(3, 5, 15);g.addEdge(4, 6, 2);g.addEdge(5, 6, 6);g.shortestPath(0);return 0;
}