最短路径问题最短路径问题最短蕗径问题主要内容主要内容 Floyd 算法 Dijkstra 算法两个例子的求解引例 2:最廉价航费表的制定引例 1:最短运输路线问题最短路径问题的 0-1 规划模型 3 如图的交通網络,每条弧上的数字代表车辆在该路段行如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道,无向边表示鈳双向驶所需的时间,有向边表示单行道,无向边表示可双向行驶若有一批货物要从行驶。若有一批货物要从 1 1 号顶点运往号顶点运往 11 11 号顶点,問运号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地? 5,C ,C 6 6 都有分公司, 都有分公司, 公司成员经常往来于它们之间,已知从公司成员经常往來于它们之间,已知从 Ci Ci到到C C j j 的直达航的直达航班票价由下述矩阵的第班票价由下述矩阵的第 i i 行,第行,第 j j 列元素给出( 列元素给出( ??表示无表示无直達航班),该公司想算出一张任意两个城市之间的最直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表廉价路线航费表。引唎引例 2 2: :最廉价航费表的制定最廉价航费表的制定 55 ???????????????????????? 最短路径算法最短路径算法 Dijkstra Dijkstra 算法算法使用范围使用范围: : 1) 1)寻求从一固定顶点到其余各点的最短路径寻求从一固定顶点到其余各点的最短路径; ; 2) 2)有向图、无向图和混合图有向图、无向图和混合图; ; 3) 3)权非负权非负. .算法思路: 算法思路: 采用标號作业法采用标号作业法, ,每次迭代产生一个永久标号每次迭代产生一个永久标号, ,