數(shù)據(jù)與計(jì)算機(jī)通信中文版課后答案(編輯修改稿)
2025-07-21 06:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 =s) L[h][i]=∞。 R[i]=s。 } L[h][s]=0。 while (!ISFinished) { n++。 L[h][s]=0。 for (ini=0。in。i++) { temp=∞。for(int x=0。in。x++){ if((L[h1][x]+A[x][i])temp) { y=x。temp=L[h1][x]+A[x][i]。 } } if(tempL[h1][i]) { R[i]=y。 L[b][i]=temp。 } ISFinished=true。 For(int j=0。jn。j++) { if(L[h1][j]!=L[h][j]) ISFinished=false。 } }//while。 另一種答案：? BELLMANFORD(G)? for each vertex u in V initialize vertex u ? d[u] := infinity? p[u] := 0? end for ? d[s] := 0 ? for i := 1 to V1 ? for each edge (u,v) in E examine edge (u,v)? if (d[u] + w(u,v) d[v])? d[v] := d[u] + w(u,v) ? p[u] := u? end if? end for? end for? for each edge (u,v) in E ? if (w(u,v) + d[u] d[v])? return (false, , ) edge (u,v) was not minimized ? else ? … edge (u,v) was minimized ? end for? return (true, p, d)―――――――――――――――――――――――――――――――――L_current[0] = 0。for (v = 1。 v n。 v++) L_current[v] = w[0][v]。do { fixed_count = 1。 for (v = 1。 v n。 v++) { L_new[v] = L_current[v]。 for (u = 0。 u n。 u++) if (L_current[u] + w[u][v] L_new[v]) L_new[v] = L_current[u] + w[u][v]。 if (L_new[v] == L_current[v]) fixed_count++。 }} while (fixed_count n)。 10．14答案 Dijstra算法和Bellman算法總是能夠得到相同的結(jié)果；（1） Dijstra算法科得到一條最小路徑，則從其源端點(diǎn)到目的點(diǎn)必有一條路經(jīng)，于是BellmanFord算法必能找出此路徑，因此由Dijstra找出的最小路徑必可由BellmanFord找到。（2） 若由BellmanFord算法可得到一最小路徑，則不論其路徑數(shù)為多少，都必須經(jīng)過(guò)一定數(shù)目的結(jié)點(diǎn)，于是Dijstra算法又將遍歷所有結(jié)點(diǎn)，所以此路徑經(jīng)過(guò)結(jié)點(diǎn)都將由Dijstra描述過(guò)，則此路徑必將包括在Dijstra算法的結(jié)果中。實(shí)際上，BellmanFord算法類似于洪泛式的算法，而Dijstra則是按部就班，步步為營(yíng)，兩者方法不同，結(jié)果卻完全吻合。10．15答案 證明： （1）當(dāng)n＝0時(shí)，顯然有； （2）假設(shè)當(dāng)n=k時(shí)，對(duì) 則顯然＝，否則，設(shè)存在一條更小的路徑，其頂點(diǎn)必由出發(fā)經(jīng)n頂點(diǎn)而到達(dá)j，顯然此頂點(diǎn)n落在，不然不為最小路徑，與已知相矛盾， 綜上所述，原命題成立。 10．10答案TL(1)L(3)L(4)L(5)L(6)1{2}332∞∞2{2,4}3323∞3{
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1