Dijkstra算法用于解决最短路径问题

最短路问题之Dijkstra算法

• 最短路径特性
  • 算法流程
  • 无向图示例题
  • Python代码段
  • Matlab代码段
  • Python图论库networkx

最短路性质

在图中，
用符号(u_k,u_m)_l表示连接顶点u_k与u_m之间的第l条通路，
其中(u_k,u_m)_l上的权值总和记作\left|(u_k,u_m)_l\right|，
定义从顶点v_0到顶点vn的最短路径为\left(v_0,v_n\right)_{s}，
其中s=\argmin_l\left|\left(v_0,v_n\right)_l\right|，
则对于该最优通路上任意两顶点v_p, v_q，
有\left|\left(v_p,v_q\right)_{s}\right|=\min_l\left|\left(v_p,v_q\right)_l\right|，
由此可见，在最优路径上选取任意连续两点间的子段仍构成一条最优子路径。

算法步骤

定义V为所有顶点的集合，并设W是一个加权邻接矩阵；其中W(u,v)代表顶点u至顶点v之间的权重；设定起始顶点为u_0

初始化：首先定义节点集合S = \{\nu_0\}并将其包含于图中；同时将其余所有节点归入其补集$\overline S