🍠Dijkstra算法 | 迪杰斯特拉算法-迷宫解算器可视化
Dijkstra算法 | 迪杰斯特拉算法 | Python | C++ | Java | JavaScript | C#
Dijkstra算法
该算法维护一组已访问的顶点和一组未访问的顶点。 它从源顶点开始，迭代地选择距源具有最小暂定距离的未访问顶点。 然后，它访问该顶点的邻居，如果找到更短的路径，则更新它们的暂定距离。 这个过程一直持续到到达目的地顶点，或者所有可到达的顶点都被访问过。
在许多应用中都需要 Dijkstra 算法，其中找到两点之间的最短路径至关重要。 例如，它可以用于计算机网络的路由协议，也可以用于地图系统来查找起点和目的地之间的最短路径。
Dijkstra 算法可以适用于有向图和无向图，因为该算法被设计为适用于任何类型的图，只要它满足具有非负边权重和连通性的要求。
在有向图中，每条边都有一个方向，表示边所连接的顶点之间的行进方向。在这种情况下，算法在搜索最短路径时遵循边缘的方向。
在无向图中，边没有方向，算法在搜索最短路径时可以沿着边向前和向后遍历。
算法过程
将当前距离标记为 0 的源节点，将其余节点标记为无穷大。
将当前距离最小的未访问节点设置为当前节点。
对于每个邻居，当前节点的N加上相邻节点的当前距离以及连接0->1的边的权重。如果小于Node当前距离，则将其设置为新的N当前距离。
将当前节点 1 标记为已访问。
如果还有未访问的节点，则转步骤2。
实现方式
实现 Dijkstra 算法的方法有多种，但最常见的是：
优先级队列（基于堆的实现）
基于数组的实现
代码实现
Python:
import heapq
class Node:
def __init__(self, v, distance):
self.v = v
self.distance = distance
def __lt__(self, other):
return self.distance < other.distance
def dijkstra(V, adj, S):
visited = [False] * V
map = {}
q = []
map[S] = Node(S, 0)
heapq.heappush(q, Node(S, 0))
while q:
n = heapq.heappop(q)
v = n.v
distance = n.distance
visited[v] = True
adjList = 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 = v
sn.distance = distance + adjLink[1]
heapq.heappush(q, Node(adjLink[0], distance + adjLink[1]))
result = [0] * V
for i in range(V):
result[i] = map[i].distance
return result
def main():
adj = [[] for _ in range(6)]
V = 6
E = 5
u = [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 = 1
result = dijkstra(V, adj, S)
print(result)
if __name__ == "__main__":
main()
C++:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
class Graph {
int V; // No. of vertices
list<pair<int, int> >* adj;
public:
Graph(int V); // Constructor
void 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;
}
迷宫解算器可视化
源代码
Last updated