文档介绍：定义１ 设 G ＝ (V, E)是简单图，若对于每一个e∈Ｅ，均有一正实数W(e)与之对应，则称W是G的权函数，并称G为带权图，记为 G ＝ (V, E, W)。
我们研究带权图，一个重要的内容就是寻找某类具有最小（最大）权的子图，其中之一就是最短路问题，例如：给定一个连接各城市的铁路网络（连通的带权图），在这个网络中的两个指定的城市之间确定一条最短路。
定义２ 设G ＝ (V, E, W)是带权图，μ＝(ei1,ei2,……eik)是G中的一条路，μ的路长为W(μ)＝∑W(ei)。从u到v的最短路P是指满足下列条件的路
W(P) ＝ min{W(μ)|μ为从u到v的路}
由上述定义可以看到，如果每条边的权函数值为1，则带权图的路长与一般图的路长是一致的。
§５ 带权图的最短路径
1
，这是至
今公认的求最短路长的最好算法，我们称它为Dijkstra算法。
Dijkstra算法
功能：在连通的带权图中，求从v0到v的最短路的路长。
No1. p0 ＝ v0；P ＝ {v0}；T ＝ V\{v0}; d(p0) ＝ 0；
( t∈T)(d(t) ＝ ∞)；
No2. ( t∈T)(d(t) ＝ min(d(t)，d(p0)+W(p0,t))；
No3. 在T中选取t0, 使( t∈T)(d(t0)≤d(t))；
No4. p0 ＝ t0 ；P ＝ P{t0}；T ＝ T\{t0}；
No5. if p0 ≠ v then goto No2 else end。
2
例1.  求图1中从v0到v5的最短路径.
1. p0 ＝ v0, P ＝ {v0}, T ＝ {v1,v2,v3,v4,v5}
d(p0) ＝ 0, d(v1) ＝ d(v2) ＝ d(v3) ＝ d(v4) ＝ d(v5) ＝ ∞.
2. d(v1) ＝ 1, d(v2) ＝ 4, d(v3) ＝ d(v4) ＝ d(v5) ＝ ∞.
3. t0 ＝ v1
4. p0＝ t0 ＝ v1, P ＝ {v0,v1}, T ＝ {v2, v3,v4,v5}.
5. p0≠v5 , GoTo 2.
2. d(v2) ＝ 3, d(v3) ＝ 8, d(v4) ＝ 6, d(v5) ＝ ∞.
3. t0 ＝ v2
4. p0＝ t0 ＝ v2, P ＝ {v0,v1,v2}, T ＝ {v3,v4,v5}
5. p0≠v5 , GoTo 2.
v0
v2
v1
v3
v4
v5
1
4
2
5
7
1
3
2
6
3
2. d(v3) ＝ 8, d(v4) ＝ 4, d(v5) ＝ ∞.
3. t0 ＝ v4.
4. p0 ＝ t0 ＝ v4, P ＝ {v0,v1,v2, v4}, T ＝ {v3, v5}.
5. p0≠v5, GoTo 2.
2. d(v3) ＝ 7, d(v5) ＝ 10.
3. t0 ＝ v3
4. p0 ＝ t0 ＝ v3, P ＝ {v0, v1, v2, v3, v4}, T ＝ {v5}
5. p0 ≠ v5, GoTo 2.
2. d(v5) ＝ 9.
3. t0 ＝ v5.
4. p0 ＝ t0 ＝ v5, P ＝ {v0,v1,v2,v3,v4,v5}, T ＝ { }.
5. p0 ＝ v5 .
4
Dijkstra算法的基本思想是：将图 G 中结点集合 V 分成两部分，一部分称为具有 P 标号的集合，另一部分称为具有 T 标号的集合。所谓结点ａ的 P标号是指从 v0 到ａ的最短路的路长，而结点ｂ的Ｔ标号是指从 v0 到ｂ的某条路径的长度。Dijkstra算法中首先将 v0 取为 P 标号结点，其余的点均为 T 标号结点，然后逐步地将具有 T 标号的结点改为 P 标号结点，当结点 v 也被改为 P 标号时，就找到了从 v0 到v 的最短路径的长度。
5
§6 Euler图
Euler图的来历为konigsberg七桥问题 。
定义1 设 G ＝ (V, E) 是无向连通图。
1) 若存在一条路 P，此路通过 G 中每条边且仅一次，则称此路为Eu