图论一．最短路问题问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。
最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。
将问题抽象为赋权有向图或无向图G ，边上的权均非负 对每个顶点定义两个标记（()l v ，()z v ），其中：()l v ：表示从顶点到v 的一条路的权 ()z v ：v 的父亲点，用以确定最短路的路线S ：具有永久标号的顶点集1.1Dijkstra 算法：即在每一步改进这两个标记，使最终()l v 为最短路的权 输入：G 的带权邻接矩阵(,)w u v 步骤：（1） 赋初值：令0()0l u =，对0v u ≠，令()l v =∞，0={u }S ，0i =。
（2） 对每个(\)i i i v S S V S ∈=（即不属于上面S 集合的点），用min{(),()()}iu S l v l u w uv ∈+代替()l v ，这里()w uv 表示顶点u 和v 之间边的权值。
计算min{()}iu S l v ∈，把达到这个最小值的一个顶点记为1i u +，令11{}i i i S S u ++=⋃。
（3） 若1i V =-，则停止；若1i V <-，则用1i +代替i ，转（2）算法结束时，从0u 到各顶点v 的距离由v 的最后一次编号()l v 给出。
在v 进入i S 之前的编号()l v 叫T 标号，v 进入i S 之后的编号()l v 叫P 标号。
算法就是不断修改各顶点的T 标号，直至获得P 标号。
若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各顶点的最短路也在图上标示出来了。
理解：贪心算法。
选定初始点放在一个集合里，此时权值为0初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。
然后以新纳入的点为起点继续搜索，直到所有的点遍历。
§9.2 循环比赛的排名问题问题：n 支球队参加循环比赛，两两交锋，一场决胜，不容平局，“0、1”打分。
如何排名？1．竞赛图：每对顶点之间有且只有一条有向边相连的有向图；有向边指向负方。
2．路径与完全路径：称有向图),(E V G 的一个顶点序列k i i i i v v v v 210为图),(E V G 的一条步长为k 的路径，若满足：对k j k ≤≤∀1,，均有E v v j j i i ∈-1；若还满足k i i v v =0，则称之为图),(E V G 的一条步长为k 的回（或闭）路径。
而若顶点集V 的一个全排列1210-n i i i i v v v v 构成图),(E V G 的一条路径，也称之为图),(E V G 的一条完全路径。
● 图1中：6431v v v v 、16431v v v v v 、1654321v v v v v v v 、654321v v v v v v ● 子路径、闭的完全路径3．定理：任一)2(≥∀n n 阶竞赛图),(E V G 都存在完全路径。
证明（数学归纳法）：1：2=n 时，如图3-0，命题真；2：设k n =时命题真；3：当1+=k n 时，设{}121,,,+=k k v v v v V 为顶点集，记{}k v v v V ,,21~=，~G 为图),(E V G 关于{}k v v v V ,,21~=的生成子图；由归纳假设2，在~G 中存在完全路径，不失一般性，设k k v v v v 121...-为~G 中的一条完全路径，考虑顶点1+k v 与{}k v v v V ,,21~=的邻接关系，有如下三种情形：图3-1：k k k v v v v v 1211...-+为G 中的一条完全路径；图3-2：1121...+-k k k v v v v v 为G 中的一条完全路径图3-3：k k i k i v v v v v v v 11121......-+-为G 中的一条完全路径。
