基于Dijkstra算法优化的城市交通路径分析

　　Dijkstra算法是1959年由荷兰计算机科学家Dijkstra提出的图论中求最短路径的常用算法[], 该算法可求得图中一点到其他任一顶点的最短路径[].Dijkstra算法将网络节点分成3部分:未标记节点、临时标记节点和永久标记节点.在网络图中, 将所有节点初始化为未标记节点, 在搜索过程中游历节点和任一路径中相连通的节点为临时标记节点, 每次循环都是把从临时标记节点中搜索距起源点路径长度最短的节点作为永久标记节点, 直至找到目标节点或者所有的节点都成为永久标记节点后才算法结束.如图1所示, 假设节点网络的起源点为节点0, 目标点为节点4, 求节点0到节点4最短路径的距离(各节点间的长度是假设的). 　　假设每个节点都有一对标号(wi, pj), wi是起源点到目标点的最短路径的长度, wj是从起源点s到任意节点j的最短路径长度(从顶点到其本身的最短路径是零路(没有弧的路), 其长度等于零), pj为从起源点s到节点j的最短路径中j点的前一节点.求解从起源点i到目标节点j的最短路径, 基本过程如下: 　　1)初始化.起源点设置为 　　①若起源点s最短路径长度ws=0, ps为空; 　　②所有其他节点的路径长度wi=¥ , pi=s; 　　③标记起源点s.记所有已标记的节点k=s, 其他节点设为未标记的. 　　2)检验从所有已标记的节点k到其直接连接的未标记节点j的距离, 并设置 　　wj=minwj, wk+dkj(1) 　　式中:wj是未标记节点j的最短路径长度; wk是已标记节点k的最短路径长度; dkj是从节点k到节点j的直接连接距离. 　　3)选取下一个点.从所有未标记的节点wj中, 选取最小的一个标记节点i, 即wi=minwj(所有未标记的节点j), 节点i就被选为最短路径中的一点, 并设为已标记的点. 　　4)找到节点i的前一点.从已标记的节点中找到直接连接到节点i的点j', 作为前一点, 设置i=j'. 　　5)标记点i.如果所有节点已标记, 则算法求出最短路径(见表1); 否则, 记k=i, 转到步骤2)再继续.