茶年 · 中文维基百科

戴克斯特拉算法

Wikipedia · 2026-05-29 维基百科 👁 1 阅读

{{Infobox algorithm
|class=搜索算法
|image=Dijkstra Animation.gif
|caption = 戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。
|data=图
堆/优先队列（算法优化）
|best-time=
|average-time=
|SpaceComp=O(|E|+|V|)（使用邻接表存储边的情况），是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题。

该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。具体来说，戴克斯特拉算法设置了一顶点集合S，在集合S中所有的顶点与源点s之间的最终最短路径权值均已确定。

戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是的一个特例。

下面是一些戴克斯特拉算法经典实现的复杂度比较：

正确性证明
，戴克斯特拉算法的发现者]]
戴克斯特拉本人在他的论文中给出了一份简单的证明。他的目标是让不去实际计算的人也能理解这个问题和解决的方法，于是他在发现了这个算法之后在ARMAC上做了简单实验。

戴克斯特拉算法及其改进算法应用广泛，尤其是在寻路、交通、规划中。

如果有已知信息可用來估計某一點到目標點的距離，則可改用A搜尋算法，以減小最短路徑的搜索範圍，戴克斯特拉算法本身也可以看作是A搜索算法的一个特例。

戴克斯特拉算法本身采用了与Prim算法类似的贪心策略。快速行进算法与戴克斯特拉算法同样有相似之处。

参考源程序
以下是该算法使用堆优化的一个C++实现参考：

// 無向圖
#include
using namespace std;
#define INF 0x3f3f3f3f

// iPair ==> Integer Pair（整数对）
typedef pair iPair;

// 加边
void addEdge(vector> adj[], int u, int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}

// 计算最短路
void shortestPath(vector> adj[], int V, int src)
{
// 关于stl中的优先队列如何实现，参考下方网址：
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue, greater> pq;

// 距离置为正无穷大
vector dist(V, INF);
vector visited(V, false);

// 插入源点，距离为0
pq.push(make_pair(0, src));
dist[src] = 0;

/ 循环直到优先队列为空 /
while (!pq.empty())
{
// 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点
int u = pq.top().second;
pq.pop();
if (visited[u])
{
continue;
}
visited[u] = true;
// 遍历所有边
for (auto x : adj[u])
{
// 得到顶点边号以及边权
int v = x.first;
int weight = x.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 adj[V];
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);

shortestPath(adj, V, 0);

return 0;
}

以下是该算法Python的一个实现：

import sys
max = sys.maxsize

vertices_number = 6
adjacency_matrix = [
[0, 1, 10, -1, -1, 2],
[10, 0, 1, -1, -1, -1],
[1, 10, 0, -1, -1, -1],
[-1, -1, 2, 0, 1, 10],
[-1, -1, -1, 10, 0, 1],
[-1, -1, -1, 1, 10, 0]]
start = []
dest = ["2", "5"]
key = []

def init_keys(s: int):
global key
key = [ max ] * vertices_number
key[s] = 0

def dijkstra(from_vertex, dest_vertex):
fid = int(from_vertex) - 1
tid = int(dest_vertex) - 1
init_keys(fid)
rel = [fid]
min_vertex = fid
hop_path = {}

while len(rel) 0 \
and key[i] > key[min_vertex] + adjacency_matrix[min_vertex][i]:
key[i] = key[min_vertex] + adjacency_matrix[min_vertex][i]
hop_path.update({i + 1: {"from": min_vertex + 1, "cost": adjacency_matrix[min_vertex][i]}})

if min_vertex not in rel:
rel.append(min_vertex)

min_vertex = tid
for i in range(vertices_number):
if i not in rel and key[i] {}".format(str(next_hop), cost ,path_str)
path_str = "{} -({})-> {}".format(str(hop_path[next_hop]["from"]), hop_path[next_hop]["cost"], path_str)

return key[tid], path_str

def find_shortest_router():
for s in start:
print("Forwarding Table for {}".format(s))
print("{:>10} {:>10} {}".format("To", "Cost", "Path"))
for d in dest:
c, n = dijkstra(s, d)
print("{:>10} {:>10} {}".format(d, c, n))

def main():
for i in range(1, vertices_number + 1):
if str(i) not in dest:
start.append(str(i))
find_shortest_router()

if __name__ == '__main__':
main()

参见

  • 图论
  • A*搜尋演算法
  • 贝尔曼-福特算法
  • 宽度优先搜索
  • Flood fill
  • Floyd-Warshall算法
  • 最长路径问题

參考
参考文献
扩展阅读
*
*
*
*
*
*
*
*
*

外部連結

#带有伪代码示例的条目 #艾兹赫尔·戴克斯特拉 #搜尋演算法 #组合优化 #图算法 #路由算法 #圖算法

评论 (0)

  • 还没有评论，来抢沙发吧。