复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)16/30

5.4 Shortest-path problem Let G=(v,E, w) be a weighted connected simple graph, w is a function from edges set E to position real numbers set. We denoted the weighted of edge i, by w(i,j, and w(i,j)=+oo when JEE 4 Definition 21: Let the length of a path p in a weighted graph G=(V,E, w) be the sum of the weights of the edges of this path. We denoted by w(p). The distance between two vertices u and v is the length of a shortest path between u and v, we denoted by d(u, v). u=y min w(p)l pis a path between u and v, there is a path between u and v P
5.4 Shortest-path problem ❖ Let G=(V,E,w) be a weighted connected simple graph, w is a function from edges set E to position real numbers set. We denoted the weighted of edge {i,j} by w(i,j), and w(i,j)=+ when {i,j}E ❖ Definition 21: Let the length of a path p in a weighted graph G =(V,E,w) be the sum of the weights of the edges of this path. We denoted by w(p). The distance between two vertices u and v is the length of a shortest path between u and v, we denoted by d(u,v). = = w p p is a path between u and v there is a path between u and v u v d u v p min { ( )| } 0 ( , )

今 Dijkstra’ s algorithm( E W.Dijkstra) .o Let G=(V,E, w) and VEn where W>0. Suppose that s is a nonempty subset of Vand y∈S.LetT=Vs Example: Suppose that (u. s a shortest path between u andv。 Then(u,v,v",v)is a L, shortest path between u and v
❖ Dijkstra’s algorithm (E.W.Dijkstra) ❖ Let G=(V,E,w) and |V|=n where w>0. Suppose that S is a nonempty subset of V and v1S. Let T=V-S. Example: Suppose that (u,v',v'',v''',v) is a shortest path between u and v. Then (u,v',v'',v''') is a shortest path between u and v

o Let VET. l(v be the length of a shortest path from vI to v containing only vertices in s
❖ Let vT. l(v) be the length of a shortest path from v1 to v containing only vertices in S

6 7 2 Example: S=a, bj, 3 5 2T={c,d,e,2 lc a-c: ac 4 a.b.c 3 l(c)=3。 (e)= be 6 令a,b,C,e4,l(e)=4?× Note: l(v) is the length of a shortest path from vI to v containing only vertices in S 令le)=6,l(d)=8 (2)=00
❖ l(e)=? ❖ a,b,e 6; ❖ a,b,c,e 4, l(e)=4?。 ❖ Note:l(v) is the length of a shortest path from v1 to v containing only vertices in S. ❖ l(e)=6, l(d)=8 ❖ l(z)=。 Example : S={a,b}, T={c,d,e,z} l(c): a→c:a,c 4 a,b,c 3, l(c)=3

令l(C)=3,l(e)=6,l(d)=8,l(z)=∞o o minverl(v=lc=3 is the length of a shortest path from a to c. 8 Theorem 5.12: Suppose that mineT l(v)) l(V). Then the length of the shortest path from v, to v'is /(v)
❖ l(c)=3,l(e)=6, l(d)=8, l(z)=。 ❖ minvT {l(v)}=l(c)=3 is the length of a shortest path from a to c. ❖ Theorem 5.12:Suppose that minvT {l(v)}= l(v'). Then the length of the shortest path from v1 to v' is l (v')

o Proof: Suppose that there is a path p from v, to and the length of this path less than l(v) Then the path p must conclude some vertices of Vi 路
❖ Proof: Suppose that there is a path p from v1 to v', and the length of this path less than l(v'). ❖ Then the path p must conclude some vertices of T-{v'}

令l(v)? 令(1)S={v1},T=V-{v1,forv∈T W,ν){,吟∈E l()= otherwise (2)For SCV, T=v-S, suppose that these vertices of the shortest paths from vi to any vertices of s are in S. By Theorem 5.12(minver(v)=lVR, VKET), we gained the result which I(vR is the length of the shortest path from v, to vk(distance)o The vertex v is added to s (Let S=SUlk, T=T-VR, VET. Suppose that /(v) is the length of a shortest path from v, to v containing only vertices in S. Then /'(v)=min(l(v), l(vk)+w(vRv) (4Let S=S,T=T,l(v=l(v), goto(2)
❖ l(v)? ❖ (1) S={v1 },T=V-{v1 },for vT (2)For SV, T=V-S, suppose that these vertices of the shortest paths from v1 to any vertices of S are in S. By Theorem 5.12(minvT{l(v)}=l(vk ), vkT), we gained the result which l(vk ) is the length of the shortest path from v1 to vk (distance)。The vertex vk is added to S. (3)Let S'=S∪{vk }, T'=T-{vk }, vT'. Suppose that l'(v) is the length of a shortest path from v1 to v containing only vertices in S'. Then l'(v)=min{l(v),l(vk )+w(vk ,v))} (4)Let S=S',T=T', l(v)=l'(v), goto (2) + = otherwise w v v v v E l v ( , ) { , } ( ) 1 1

7 5 6 S=a,b,=c,d, e, z 令l(c)=3,l(e)=6,l(d)=8,l(z)=+∞o 令 mInuet{(v)}=l(c)=3 s’={a,b,c},T={d,e, 6o e=min(e), l(c)+w(c, e)=4, oo l'(d=min l(d), l(c)+w(c, d)=8, w(c,d)=+∞ 令I(z)=min{(z),l(c)+w(C,2)}=+
❖ S={a,b},T={c,d,e,z} ❖ l(c)=3,l(e)=6, l(d)=8, l(z)=+。 ❖ minvT{l(v)}=l(c)=3 ❖ S’={a,b,c}, T’={d,e,z} ❖ l'(e)=min{ l(e), l(c)+w(c,e)}=4, ❖ l'(d)=min{l(d), l(c)+w(c,d)}=8, ❖ w(c,d)= + ❖ l'(z)=min{l(z), l(c)+w(c,z)}= +

令 Theoren513:Forv∈T,P(v)=min{v), +WVKs v)I 令 Proof:Lets=su{v o Suppose that /'(v) is the length of a shortest path from vI to v containing only vertices in S o(1There are some paths from vi to v, but these paths don't contain the vertex v, and other vertices of t. Then l(v) is the length of the shortest path of these paths, i.e. (v)=(v) 4s(2)There are some paths from v, to v, these paths from vI to Vk don't contain other vertices of T, and the vertex Vk adjacent edge vkv. Then l(v+w(vk,v) is the length of the shortest path of these paths, viz l'(v=l(vR+w vkv)
❖ Theorem 5.13: For vT‘, l’(v)= min{l(v), l(vk )+w(vk , v)} ❖ Proof: Let S'=S∪{vk }. ❖ Suppose that l‘(v) is the length of a shortest path from v1 to v containing only vertices in S’. ❖ (1)There are some paths from v1 to v, but these paths don’t contain the vertex vk and other vertices of T'. Then l(v) is the length of the shortest path of these paths, i.e. l'(v)=l(v)。 ❖ (2)There are some paths from v1 to v, these paths from v1 to vk don’t contain other vertices of T', and the vertex vk adjacent edge {vk ,v}. Then l(vk )+w(vk ,v) is the length of the shortest path of these paths, viz l'(v)= l(vk )+w(vk ,v)

冷(1)LetS=,T=V,l(v1)=0,forv≠v1and (v)=+o Let ke1 冷(2)S=S∪{vk},T=T-{vk}, . 8 For each vertex y of t 令(v=min{(v),v1)+w(v12v)}; 令()-(v),S->S,TT。 &3)minveTl(v=l(vk+u %(4)if k=n-1, then stop 4. if k<n-1, then k+l-k goto(2)
❖ (1)Let S=,T=V,l(v1 )=0,for vv1 and l(v)=+ ❖ Let k=1 ❖ (2)S'=S∪{vk },T'=T-{vk }, ❖ For each vertex v of T', ❖ l'(v)=min{l(v),l(vk )+w(vk ,v)}; ❖ l'(v)→l(v),S'→S,T'→T。 ❖ (3)minvT {l(v)}=l(vk+1 )。 ❖ (4)if k=n-1,then stop ❖ if k<n-1,then k+1→k goto (2)
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)17/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)15/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)14/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)13/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)12/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)11/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)10/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)09/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)08/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)07/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)06/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)05/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)04/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)03/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)02/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)01/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(下)》英文课件(赵一鸣)32/32.ppt
- 复旦大学:《离散数学 Discrete Mathematics(下)》英文课件(赵一鸣)31/32.ppt
- 复旦大学:《离散数学 Discrete Mathematics(下)》英文课件(赵一鸣)30/32.ppt
- 复旦大学:《离散数学 Discrete Mathematics(下)》英文课件(赵一鸣)29/32.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)18/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)19/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)20/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)21/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)22/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)23/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)24/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)25/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)26/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)27/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)28/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)29/30.ppt
- 复旦大学:《离散数学 Discrete Mathematics(上)》英文课件(赵一鸣)30/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)01/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)02/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)03/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)04/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)05/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)06/30.ppt
- 复旦大学:《离散数学——集合与图论》PPT课件(赵一鸣)07/30.ppt