简介：
一、算法起源：从交通问题到数学抽象
20 世纪 50 年代，计算机科学尚处于萌芽阶段，图论作为离散数学的重要分支，主要用于解决路径规划、网络优化等实际问题。荷兰计算机科学家Edsger Wybe Dijkstra（1930–2002）在 1956 年遇到了一个具体需求：计算荷兰阿姆斯特丹到鹿特丹的最短交通路线。当时的地图可抽象为 “带权图”（道路为边，距离为权重），而寻找最短路径的问题亟需一种高效算法。
Dijkstra 最初尝试用手工计算解决这一问题，通过逐步扩展 “已确定最短路径的节点”，并更新相邻节点的距离。这一过程启发他将问题抽象为贪心策略的数学模型 —— 每次选择当前已知最短距离的节点作为 “扩展点”，确保每一步决策都是局部最优的，最终实现全局最优解。
二、算法的首次提出与早期研究（1956–1959）
1956 年，Dijkstra 在荷兰数学中心（Mathematisch Centrum）首次向同事展示了这一算法，但并未立即发表。直到 1959 年，他才在论文《A Note on Two Problems in Connexion with Graphs》（关于图的两个问题的注记）中正式描述了该算法。值得注意的是，这篇论文仅有两页篇幅，却奠定了现代图算法的基础。
早期的 Dijkstra 算法采用邻接矩阵存储图结构，并通过遍历未访问节点来选择下一个扩展点，时间复杂度为 O(V2)（V 为顶点数）。尽管这一效率在今天看来较为有限，但在当时的计算机算力下，已能显著提升路径计算的速度。
三、算法的传播与优化（1960–1980 年代）
随着计算机科学的发展，Dijkstra 算法逐渐成为图论中的核心内容，并在多个领域得到应用。20 世纪 60 年代，学者们开始探索算法的优化方向：
-
数据结构的引入：
- 1975 年，计算机科学家Robert Tarjan（图灵奖得主）提出使用 ** 优先队列（堆）** 优化节点选择过程。通过将未访问节点按当前最短距离维护在堆中，每次提取最小值的时间复杂度降为 O(logV)，结合邻接表存储图结构，整体时间复杂度优化至 O((V+E)logV)（E 为边数），这成为现代 Dijkstra 算法的标准实现方式。
-
并行计算与硬件加速：
- 1980 年代，随着并行计算技术的兴起，研究者尝试将 Dijkstra 算法并行化，通过多处理器同时处理节点扩展，进一步提升大规模图的计算效率。
四、算法的理论地位与争议
Dijkstra 算法的诞生并非完全孤立。在其发表前后，其他学者也在探索类似问题：
- 1957 年：美国海军研究实验室的John Robinson Floyd提出了计算所有节点对最短路径的 Floyd 算法，与 Dijkstra 算法形成互补。
- 1959 年：苏联数学家Lev G. Khachiyan（后来因线性规划多项式算法闻名）在未受 Dijkstra 影响的情况下，独立提出了类似的最短路径算法，但因冷战时期学术交流受限，其成果未被西方广泛认知。
此外，Dijkstra 本人曾在晚年对算法的命名提出过谦逊的看法：“我从未将这个算法称为‘我的’算法，它属于那个时代的集体智慧。” 这一态度折射出早期计算机科学研究者对学术合作的重视。
五、跨领域应用与现代发展（1990 年代至今）
随着互联网和复杂系统研究的兴起，Dijkstra 算法的应用场景不断扩展：
-
计算机网络：
- 作为 OSPF（开放最短路径优先）路由协议的核心，用于路由器间的路径计算，确保数据包高效传输。
-
地理信息系统（GIS）：
- 谷歌地图、高德地图等导航工具均基于 Dijkstra 算法（或其变种）实现实时路径规划，结合交通数据动态调整权重（如路况拥堵程度）。
-
人工智能与机器人：
- 机器人路径规划中，将环境建模为图结构（节点为可行区域，边为移动路径），利用 Dijkstra 算法寻找无障碍最短路径。
-
生物信息学：
- 在蛋白质结构分析中，通过图模型模拟分子间相互作用，算法用于计算分子构象的能量最优路径。
-
算法优化与变体：
- 针对大规模图（如社交网络、交通网络），衍生出分层 Dijkstra 算法（HLA）、收缩层次算法（CH）等，通过预处理节点层次结构，将查询时间复杂度降至近线性。
六、Dijkstra 与计算机科学的遗产
Edsger Dijkstra 不仅是算法的发明者，更是计算机科学方法论的先驱。他提出的 “结构化程序设计” 思想（如避免 GOTO 语句）深刻影响了现代编程范式，而 Dijkstra 算法则成为其学术生涯的重要注脚。1972 年，他因在操作系统、程序设计语言和算法领域的贡献获得图灵奖，颁奖词中特别提及了这一算法对计算机科学的基础性作用。
核心思想
- 贪心策略：从源点出发，逐步向外扩展最短路径。每次选择当前已知的最短距离顶点，并通过该顶点更新其邻接顶点的距离（松弛操作）。
- 松弛操作：对于顶点 u 的邻接顶点 v，若通过 u 到达 v 的路径更短（即 dist[u]+weight(u,v)<dist[v]），则更新 dist[v]。
关键步骤
-
初始化：
- 用数组
dist[]记录源点到各顶点的最短距离，初始时源点距离为 0，其余为 无穷大。 - 使用优先队列（最小堆）维护待处理顶点，按当前最短距离排序。
- 用数组
-
循环扩展最短路径：
- 从优先队列中取出距离最小的顶点 u，标记为 “已确定最短路径”。
- 遍历 u 的所有邻接顶点 v，更新 v 的最短距离（松弛操作），并将 v 重新加入优先队列。
-
终止条件：所有顶点的最短路径确定后，
dist[]数组即保存最终结果。
时间复杂度
- 朴素实现（邻接矩阵 + 遍历）：O(V2)（V 为顶点数）。
- 优化实现（邻接表 + 优先队列）：
- 二叉堆：O((V+E)logV)（E 为边数）。
- 斐波那契堆：O(E+VlogV)（理论最优，实际较少用）。
应用场景
- 路径规划：导航系统（如地图导航）计算最短路线。
- 网络路由：路由器寻找数据传输的最优路径。
- 图论扩展：资源分配、最小生成树（需结合其他算法）等。
局限性与替代方案
-
局限性：
- 无法处理负权边（可能导致循环更新或错误结果）。
- 对大规模图（顶点数极高）效率有限。
-
替代算法：
- 负权图：Bellman-Ford 算法（支持负权，但时间复杂度较高）或 Johnson 算法（处理大规模负权图）。
- 稀疏图优化：使用更高效的优先队列（如跳表、配对堆）。
示例（c++）：
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef pair<int, int> ii;
// Dijkstra 算法实现
vector<int> dijkstra(const vector<vector<ii>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, numeric_limits<int>::max());
dist[start] = 0;
// 优先队列，存储 (距离, 顶点) 对
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
// 如果当前距离大于已知最短距离，跳过
if (d > dist[u]) continue;
// 遍历邻接顶点
for (const auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
// 松弛操作
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
int n = 5; // 顶点数量
vector<vector<ii>> graph(n);
// 添加边
graph[0].emplace_back(1, 4);
graph[0].emplace_back(2, 2);
graph[1].emplace_back(0, 4);
graph[1].emplace_back(2, 1);
graph[1].emplace_back(3, 5);
graph[2].emplace_back(0, 2);
graph[2].emplace_back(1, 1);
graph[2].emplace_back(3, 8);
graph[2].emplace_back(4, 3);
graph[3].emplace_back(1, 5);
graph[3].emplace_back(2, 8);
graph[3].emplace_back(4, 6);
graph[4].emplace_back(2, 3);
graph[4].emplace_back(3, 6);
int start = 0; // 源点
vector<int> dist = dijkstra(graph, start);
// 输出结果
for (int i = 0; i < n; ++i) {
cout << "从顶点 " << start << " 到顶点 " << i << " 的最短距离是: ";
if (dist[i] == numeric_limits<int>::max()) {
cout << "无穷大" << endl;
} else {
cout << dist[i] << endl;
}
}
return 0;
}
Pascal示例：
type
bool=array[1..10]ofboolean;
arr=array[0..10]ofinteger;
var
a:array[1..10,1..10]ofinteger;//存储图的邻接数组，无边为10000
c,d,e:arr;//c为最短路径数值,d为各点前趋,
t:bool;//e：路径，t为辅助数组
i,j,n,m:integer;
inf,outf:text;
procedure init;//不同题目邻接数组建立方式不一样
begin
assign(inf,inputfile);
assign(outf,outputfile);
reset(inf);
rewrite(outf);
read(inf,n);
for i:= 1 to n do
begin
for j := 1 to n do
begin
read(inf,a[i,j]);
if a[i,j]=0 then
a[i,j]:=10000;
end;
end;
end;
procedure dijkstra(qi:integer;t:bool;varc{,d}:arr);
//qi起点,{}中为求路径部分,不需求路径时可以不要
var
i,j,k,min:integer;
begin
t[qi]:=true;
//t数组一般在调用前初始,除起点外所有节点都化成false,也可将部分点初始化成true以回避这些点
for i:= 1 to n do
d[i] := qi;
d[qi]:=0;
for i:=1 to n do
c[i]:=a[qi,i];
for i:= 1 to n-1 do
begin
min:=maxint;//改为最大值
for j:=1 to n do
if(c[j]<min) and not t[j] then
begin
k:=j;
min:=c[j];
end;
t[k]:=true;
for j:=1 to n do
if(c[k]+a[k,j]<c[j]) and not t[j] then
begin
c[j]:=c[k]+a[k,j];
d[j]:=k;
end;
end;
end;
procedure make(zh:integer;d:arr;vare:arr);//生成路径,e[0]保存路径
var
i,j,k:integer;//上的节点个数
begin
i:=0;
while d[zh]<>0 do
begin
inc(i);
e[i]:=zh;
zh:=d[zh];
end;
inc(i);
e[i]:=qi;
e[0]:=i;
end;
扫一扫
1724
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
