最短通路问题 离散数学一图论初步 南京大学计算机科学与技术系
最短通路问题 离散数学─图论初步 南京大学计算机科学与技术系
内容提要 ·引言 ●Dijkstra.算法 ·旅行商问题(TSP)
内容提要 引言 Dijkstra算法 旅行商问题（TSP）
带权图与最短通路问题 带权图：三元组(V,E,,(V,E)是图，W是从E到 非负实数集的一个函数。We)表示边e的权。 ·一条通路上所有边的权的和称为该通路的长度。 ·两点之间长度最小的通路称为两点之间的最短通路， 不一定是唯一的。 ·单源点最短路问题 给定带权图G(V,E,W并指定一个源点，确定该源 点到图中其它任一顶点的最短路（长度和路径)
带权图与最短通路问题 带权图：三元组 (V, E, W)，(V, E)是图，W是从E到 非负实数集的一个函数。W(e)表示边e的权。 一条通路上所有边的权的和称为该通路的长度。 两点之间长度最小的通路称为两点之间的最短通路， 不一定是唯一的。 单源点最短路问题 给定带权图 G(V, E, W)并指定一个源点，确定该源 点到图中其它任一顶点的最短路（长度和路径）
Dijkstra:最短路径的算法思想(1959) ●】 源点s到顶点v的最短路径若为suy,则s.u是s到u 的最短路径。 ● (-1)条最短路径按照其长度的非减次序求得，设它 们的相应端点分别为u,u1,最短路径长度记为 d(s,),i=1,n-1. ·假设前条最短路径已知，第(+1)条最短路径长度： d(s,ui+1)=minfd(s,u)+W(u,ui+1)j=1,...i}
Dijkstra最短路径的算法思想(1959) 源点s到顶点v的最短路径若为s…uv, 则s…u是s到u 的最短路径。 (n-1)条最短路径按照其长度的非减次序求得，设它 们的相应端点分别为u1 , …un-1，最短路径长度记为 d(s, ui ) ， i=1,…n-1. 假设前i条最短路径已知，第(i+1)条最短路径长度： d(s, ui+1 )=min{d(s, uj ) +W(uj , ui+1 )| j=1,…i}
求最短路径的Dijkstra算法 ●输入：连通带权图G,Vc=n,指定顶点s∈Vc ●输出：每个顶点v的标注L(y),W),其中： ·L()即从s到的最短路径长度（目前可得的） ●u是该路径上v前一个顶点
求最短路径的Dijkstra算法 输入：连通带权图G，|VG |=n, 指定顶点sVG 输出：每个顶点v的标注(L(v), u), 其中： L(v)即从s到v的最短路径长度（目前可得的） u是该路径上v前一个顶点