Dijkstra算法
Parent: ai_keywords
Dijkstra算法：核心定义与技术要点
核心定义
Dijkstra算法是一种用于带权有向图（或无向图）中求解单源最短路径的经典贪心算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。算法要求图中所有边的权重为非负值，通过逐步扩展已确定最短路径的节点集合，最终得到从源点到所有其他节点的最短距离及路径。
关键技术点
-
贪心选择策略
每次从未处理的节点中选取当前距离源点最近的节点，将其标记为已确定最短路径，并基于该节点对邻居进行松弛操作（若通过该节点可使邻居距离更短，则更新距离）。 -
优先队列优化
使用最小堆（如二叉堆）实现“选取最近节点”操作，将时间复杂度从朴素实现的O(V²)降至O((V+E)logV)，其中V为节点数，E为边数。 -
正确性基础
基于最优子结构性质：最短路径的子路径也是最短路径。同时依赖非负边权条件，保证每次贪心选择不会因后续更短路径而失效。 -
局限性
无法处理含负权边的图（此时应选用Bellman-Ford算法）；若需计算所有节点对之间的最短路径，则可使用Floyd-Warshall算法或多次运行Dijkstra。 -
变体与拓展
双向Dijkstra（从源点和终点同时搜索）、A*算法（引入启发式函数）、动态Dijkstra（应对边权变化场景）。
医学/神经科学应用场景（脑卒中纤维追踪）
在首都医科大学神经病学研究所的脑卒中研究中，Dijkstra算法被创新性地应用于扩散张量成像（DTI）数据的白质纤维束重建。具体而言：
- 将每个脑体素视为图节点，相邻体素间的局部扩散各向异性（FA值）或主方向一致性定义为边权（权越高代表连接越优）。
- 算法从缺血半暗带（病灶核心）作为源点出发，计算到对侧运动皮层或语言区功能节点的最小累积阻力路径，该路径即模拟受损纤维束的“最可能存活通路”。
- 临床价值：量化评估皮质脊髓束的损伤程度，预测患者运动功能恢复概率；或指导癫痫手术中避免切除语言相关的关键纤维连接。该算法为神经外科规划、预后判断提供了可解释的图论建模工具。
