第十一章 配送运输.

《第十一章 配送运输.》由会员分享，可在线阅读，更多相关《第十一章 配送运输.（57页珍藏版）》请在文档大全上搜索。

1、123252Dijkstra算法的基本思路是：假设每个点都有一对算法的基本思路是：假设每个点都有一对标号标号(dj,pj)，其中，其中dj是从起源点是从起源点s到点到点j的最短路的最短路径的长度径的长度(从顶点到其本身的最短路径是零路从顶点到其本身的最短路径是零路(没有没有弧的路弧的路)，其长度等于零，其长度等于零)；pj则是从则是从s到到j的最短路的最短路径中径中j点的前一点。点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1)初始化。起源点设置为：ds=0,ps为空;所有其他点:di=,pi=?;标记起源点s，记k=s,其他所有点设为未标记的。2)检验从所有已标记的点k到其直

2、接连接的未标记的点j的距离，并设置：dj=mindj,dk+lkj式中，lkj是从点k到j的直接连接距离。3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=mindj,所有未标记的点j点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2)再继续。5127563425527313571051275634255273135710512756342552731357105127563425527313571051275634255273135710251275634255273135710235127563425527313571023512756342552731357102345127563425527313571023451275634255273135710234751275634255273135710234751275634255273135710234785127563425527313571023478512756342552731357102347813512756342552731357102347813