●●● ●●●● ●●●●● ●●●● 最短路径路由 ●●●●● ●●●● 采用 Dijkstra's算法(o变种) (SPF, Shortest Path First algorithm) 基本思想是: ●选择一个源,然后考虑与其连接的节点 ●从与其连接的节点中选择最近的节点。 linwei@bbi.edu.cn
linwei@bbi.edu.cn 21 最短路径路由 ⚫ 采用 Dijkstra‘s 算法(or 变种) (SPF, Shortest Path First algorithm) 基本思想是： ⚫ 选择一个源，然后考虑与其连接的节点. ⚫ 从与其连接的节点中选择最近的节点
●●● ●●●● ●●●●● ●●●● 最短路径路由 ●●●●● ●●●● 2 A DE-dE( (,-)>D(°,-) G(6, B(2,A) c(9,B B(2,A) C(9,B) E(4,B) E(4,B) aF(°,-)>D(°,) A F(6,日)D(·,1) 864 G(5,E) H(·,-) B(2,A) C(9,B) (2,A) C(9,B) E(4,B) E(4.B) F(6,E)D()A颗 F(6,E)D(°,-) G(5,E H(9,G) G(5,E) H(8,F) The first 5 steps used in computing the shortest path from a to D The arrows indicate the working node linwei@bbi.edu.cn
linwei@bbi.edu.cn 22 最短路径路由 The first 5 steps used in computing the shortest path from A to D. The arrows indicate the working node
●●● ●●●● ●●●●● Dijsktra's算法 ●●●● ●●●●● ●●●● 1 Initialization 2N={A 3 for all nodes v 4 if v one-step reachable from a 5 then D(=c(A else D(= infinity 7 8 Loop 9 find w not in n such that d(w is a minimum 10 add w to n 11 update d(v) for all v one-step reachable from w and not in n: 2 D(v)=min( D(v), D(w)+c(w, v)) .3 / new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w tov x 15 until all nodes in N linwei@bbi.edu.cn
linwei@bbi.edu.cn 23 Dijsktra’s 算法 1 Initialization: 2 N = {A} 3 for all nodes v 4 if v one-step reachable from A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v one-step reachable from w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N
●●● ●●●● ●●●●● Dijsktra’s算法 ●●●● ●●●●● ●●●● # define maⅩ NODES1024 / maximum number of nodes * #define INFINITY 1000000000 / a number larger than every maximum path * int n, dist[MAX_NODES][MAX_NODES]; / disto0) is the distance from i to j*/ void shortest_path(int s, int t, int path) i struct state / the path being worked on * int predecessor /* previous node int length / length from source to this node * enum permanent, tentative) label; / label state * 3 state[MAX_NODES] int i, k, min struct state *p; for(p=&state[O]; p <&state[n]; p++)[/*initialize state * p→> predecessor= p->length= INFINITY; 5-8 top p->label tentative; state[t]. length =0; state[t]. label permanent; k=t /* k is the initial working node * Dijkstra's algorithm to compute the shortest path through a graph
linwei@bbi.edu.cn 24 Dijsktra’s 算法 Dijkstra's algorithm to compute the shortest path through a graph. 5-8 top
●●● ●●●● Dijsktra's算法 ●●●●● ●●●● ●●●●● ●●●● /* Is there a better path from k? * 0●0● for(i=0; i< n; i++) this graph has n nodes * if (dist(kOl=0&& state[(label = tentative)( if (state[k]. length + dist[k]0]< state[O]. length)i state[]. predecessor =k; state[]. length= state[k]. length +dist[k0 /* Find the tentatively labeled node with the smallest label. * k=O: min INFINITY. for(i=0: i< n; i++) if ( state[0]. label = tentative & state[]. length min)( min= state0length state[k] label permanent 5-8 3 while(k l= s) bottom /* Copy the path into the output array. i=0;k=s; do path[i++]=k; k= state[k predecessor; while(k>=0) Dijkstra's algorithm to compute the shortest path through a graph linwei@bbi.edu.cn
linwei@bbi.edu.cn 25 Dijsktra’s 算法 Dijkstra's algorithm to compute the shortest path through a graph. 5-8 bottom