Python实现Dijkstra算法：原理、流程与代码详解
本文详细介绍Dijkstra算法在Python中的实现。针对无负权值的有向图，通过邻接矩阵存储数据，利用辅助数组cost和path记录最短路径及前驱节点。文章逐步解析算法初始化、节点选择与路径更新流程，并提供完整Python代码及运行结果，帮助开发者掌握单源最短路径问题的解决方法。
Dijkstra算法概述
迪杰斯特拉（Dijkstra）算法主要用于处理不含负权值的有向图，旨在计算从单一指定起点到其他所有顶点的最短路径。
算法原理与数据结构
1 算法原理
该算法依据路径长度递增的顺序逐步生成最短路径。以下示例展示了一个带权值的有向图，作为程序实验的基础数据。
在程序实现中，带权有向图通过邻接矩阵graph进行存储，具体表现为一个n*n的二维数组。其中，v0至v5对应数组索引0至5，二维数组中的数值代表节点间的权值。若两节点间无法通行（例如v0到v1不可达），则设定graph[0,1]为+∞（在计算机中以最大正整数表示）。接下来探讨如何求解从v0到各节点vi的最短路径长度。
首先引入一个辅助数组cost，其元素cost[i]表示当前从起始点v0到终点vi已找到的最短路径权值（即花费）。该数组的初始状态设定为：若v0到vi存在直接弧，则cost[i]等于该弧的权值；否则，cost[i]初始化为+∞。
显然，满足cost[j]=Min_i(graph[0,i] | v_i in V)的路径即为从v0出发的最短路径，该路径为(v_0,v_j)。随后，次短路径必然是某条弧(v_0,v_i)的权值cost[i]（其中v_i属于V），或者是已确定最短路径的节点集合S中的节点cost[k]（v_k in S）与弧(v_k,v_i)权值之和。这里，V代表待求解最短路径的节点集合，S代表已求解最短路径的节点集合。
算法执行流程
2 算法流程
基于上述原理分析，以下是该算法的具体实现步骤。
初始化阶段：设置辅助数组cost，从v0出发到图中其余节点v的初始权值设定为：cost[i]=graph[0,i]（v_i属于V）；同时初始化待求节点集合S，其初始状态包含起始点，而V集合则包含除起始点外的所有节点。
选择节点v_j，使得cost[j]=Min ( cost[i] | v_i属于V-S )，此时v_j即为当前求得的从v0出发的最短路径终点。更新集合S，使S=S + V_j，并更新集合V = V - V_j。
修改从v0出发到节点集合V-S中任意顶点v_k可达的最短路径。若满足cost[j]+graph[j,k]<cost[k]，则将cost[k]更新为：cost[k]=cost[j]+graph[j,k]。
重复执行步骤2和3，直至求解集合V中的所有节点。
最短路径的存储采用一个整数数组path，其中path[i]的值记录节点vi的前一个节点索引。通过追溯path数组直至起点，即可还原从vi到起始节点的最短路径。例如，若起始节点索引为0，且path[3]=4、path[4]=0，则节点v2（注：原文此处逻辑示例可能存在笔误，通常指代路径回溯）的最短路径为v0->v4->v3。
Python代码实现与结果
3 算法实现
本节使用Python语言实现第2节所述的算法流程，关键代码如下。
3.1 最短路径代码
#!/bin/python
# -*- coding:utf-8 -*-
def dijkstra(graph, startIndex, path, cost, max):
"""
求解各节点最短路径，获取path，和cost数组，
path[i] 表示vi节点的前继节点索引，一直追溯到起点。
cost[i] 表示vi节点的花费
"""
lenth = len(graph)
v = [0] * lenth
# 初始化 path，cost，V
for i in range(lenth):
if i == startIndex:
v[startIndex] = 1
else:
cost[i] = graph[startIndex][i]
path[i] = (startIndex if (cost[i] < max) else -1)
# print v, cost, path
for i in range(1, lenth):
minCost = max
curNode = -1
for w in range(lenth):
if v[w] == 0 and cost[w] < minCost:
minCost = cost[w]
curNode = w
# for 获取最小权值的节点
if curNode == -1: break
# 剩下都是不可通行的节点，跳出循环
v[curNode] = 1
for w in range(lenth):
if v[w] == 0 and (graph[curNode][w] + cost[curNode] < cost[w]):
cost[w] = graph[curNode][w] + cost[curNode] # 更新权值
path[w] = curNode # 更新路径
# for 更新其他节点的权值（距离）和路径
return path
if __name__ == '__main__':
max = 2147483647
graph = [
[max, max, 10, max, 30, 100],
[max, max, 5, max, max, max],
[max, max, max, 50, max, max],
[max, max, max, max, max, 10],
[max, max, max, 20, max, 60],
[max, max, max, max, max, max],
]
path = [0] * 6
cost = [0] * 6
print dijkstra(graph, 0, path, cost, max)4 运行结果
[0, -1, 0, 4, 0, 3]
以上为本文全部内容，希望对读者的学习有所助益，欢迎继续支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
