演算法 › Ch4 圖論演算法
第 61 題/共 111 題 #AL-04-061 中 Shortest Path Spanning Tree 📝 ☆
Let G = ( V , E ) G=(V,E) G = ( V , E ) be an undirected connected graph, where each edge e e e has a given length l ( e ) > 0 l(e)>0 l ( e ) > 0 . Let s s s be a fixed vertex of this graph and let δ ( v ) \delta(v) δ ( v ) be the length of a shortest path from s s s to v v v . Which of the following statement(s) is(are) correct?
A (A) For each vertex v ≠ s v\ne s v = s , there is an incident edge e = ( u , v ) e=(u,v) e = ( u , v ) such that δ ( v ) = δ ( u ) + l ( e ) \delta(v)=\delta(u)+l(e) δ ( v ) = δ ( u ) + l ( e ) . B (B) For each vertex v ≠ s v\ne s v = s , choose one incident edge e = ( u , v ) e=(u,v) e = ( u , v ) such that δ ( v ) = δ ( u ) + l ( e ) \delta(v)=\delta(u)+l(e) δ ( v ) = δ ( u ) + l ( e ) ; the collection of these edges forms a spanning tree of G G G . C (C) For each vertex v ≠ s v\ne s v = s , choose one incident edge e = ( u , v ) e=(u,v) e = ( u , v ) such that δ ( v ) = δ ( u ) + l ( e ) \delta(v)=\delta(u)+l(e) δ ( v ) = δ ( u ) + l ( e ) ; the collection of these edges forms a minimum weight spanning tree of G G G . D (D) δ ( v ) > δ ( u ) + l ( e ) \delta(v)>\delta(u)+l(e) δ ( v ) > δ ( u ) + l ( e ) for some edge e = ( u , v ) e=(u,v) e = ( u , v ) . E (E) δ ( v ) ≤ δ ( u ) + l ( e ) \delta(v)\le\delta(u)+l(e) δ ( v ) ≤ δ ( u ) + l ( e ) for every edge e = ( u , v ) e=(u,v) e = ( u , v ) . 📝 寫筆記
📄 交大110
▤ 完整推導請見《WH 資工筆記 · 演算法》Ch4 圖論演算法
‹ 本章題號 · 61–80 / 111 ›
難度 全部 111 易 42 中 62 難 7
學校 全部 111 台大 30 交大 41 成大 17 中央 22