《計算機網(wǎng)絡(luò)習(xí)題與解答》

千里之行，始于足下。第2頁/共2頁精品文檔推薦《計算機網(wǎng)絡(luò)習(xí)題與解答》注意一些上標(biāo),也算是指數(shù),

10

9

為10的9次方

《計算機網(wǎng)絡(luò)習(xí)題與解答》

魯士文編

習(xí)題一

1．在下列事情下，計算傳送1000KB文件所需要的總時刻，即從開始傳送時起直到文件的最終一位到達目的地為止的時刻。假定往返時刻RTT是100毫秒，一具分組是1KB（即1024字節(jié)）的數(shù)據(jù)，在開始傳送整個的文件數(shù)據(jù)之前舉行的起始握手過程需要2×RTT

的時刻。

（a）帶寬是1.5Mbps，數(shù)據(jù)分組可延續(xù)發(fā)送。

解答：2個起始的RTT：100×2=200毫秒

傳輸時刻：RTT÷2=100÷2=50毫秒

1KB=8比特×1024=8192比特

發(fā)送時刻：1000KB÷1.5Mbps=8192000比特÷1500，000比特/秒=5.46秒

因此，總時刻等于0.2+5.46+0.05=5.71秒。

（b）帶寬是1.5Mbps，但在結(jié)束發(fā)送每一具數(shù)據(jù)分組之后，必須等待一具RTT才干發(fā)送下一具數(shù)據(jù)分組。

解答：在上一小題答案的基礎(chǔ)上再增加999個RTT

5.71+999×0.1=105.61秒

因此，總時刻是105.61秒。

（c）帶寬是無限大的值，即我們?nèi)“l(fā)送時刻為0，同時在等待每個RTT后可發(fā)送多

達20個分組。

解答：1000KB÷1KB=1000分組1000分組÷20分組=50個RTT

50-1=49個RTT

2×RTT+49RTT+0.5RTT=51.5RTT=0.1×51.5=5.15秒。

（d）帶寬是無限大的值，在緊接起始握手后我們能夠發(fā)送一具分組，此后，在第一

次等待RTT后可發(fā)送21個分組，在第二次等待RTT后可發(fā)送22個分組，。。。，在

第n次等待RTT后可發(fā)送2n個分組。

解答：取n=9

1+2+4+?+2

9

=2

9+1

-1=1023

（512-23）個分組就能夠了。

2RTT+9RTT+0.5RTT=11.5RTT

0.1×11.5=1.15秒

即總的延遲是1.15秒。

2．思考一具最大距離為2公里的局域網(wǎng)，當(dāng)帶寬等于多大時傳播延時（傳播速度為2×108米/秒）等于100字節(jié)分組的發(fā)送延時？關(guān)于512字節(jié)分組結(jié)果又當(dāng)怎么？

解答：傳播延遲等于：

2×103米÷（2×108米/秒）=10-5秒=10微秒

100字節(jié)÷10微秒=10M字節(jié)/秒=80M位/秒

512字節(jié)÷10微秒=51.2M字節(jié)/秒=409.6M位/秒

所以，帶寬應(yīng)分不等于80M位/秒和409.6M位/秒。

3．假定有一具通信協(xié)議，每個分組都引入100字節(jié)的開銷用于頭和成幀。如今使用那個協(xié)議發(fā)送1M字節(jié)的數(shù)據(jù)，但是在傳送的過程中有一具字節(jié)被破壞了，因而包含該字節(jié)的

這個分組被丟棄。試關(guān)于1000、5000、10000和20000字節(jié)的分組數(shù)據(jù)大小分不計算“開銷+丟失”字節(jié)的總數(shù)目？分組數(shù)據(jù)大小的最佳值是多少？

解答：設(shè)D是分組數(shù)據(jù)的大小，這么所需要的分組數(shù)目N=106/D

開銷=100×N（被丟棄分組的頭部也已計入開銷）

因此，開銷+丟失=100×106/D+D

分組數(shù)據(jù)大小D開銷+丟棄

1000101000

500025000

1000020000

2000025000

y=108/D+D

當(dāng)D=104時，

因此，D的最佳值是10000字節(jié)。

4．一具系統(tǒng)的協(xié)議結(jié)構(gòu)有n層。應(yīng)用程序產(chǎn)生M字節(jié)長的報文。網(wǎng)絡(luò)軟件在每層都加上h字節(jié)長的協(xié)議頭。這么，網(wǎng)絡(luò)帶寬中有多大比率用于協(xié)議頭信息的傳輸？

解答：總共有n層，每層加h字節(jié)，在每個報文上附加的頭字節(jié)的總數(shù)等于hn，所以頭消耗的有關(guān)空間所占的網(wǎng)絡(luò)帶寬的比率為hn/(M+hn)。

5．有兩個網(wǎng)絡(luò)，它們都提供可靠的面向連接的服務(wù)。一具提供可靠的字節(jié)流，另一具提供可靠的報文流。請咨詢二者是否相同？為啥？

解答：別相同。在報文流中，網(wǎng)絡(luò)保持對報文邊界的跟蹤；而在字節(jié)流中，網(wǎng)絡(luò)別做如此的跟蹤。例如，一具進程向一條連接寫了1024字節(jié)，稍后又寫了另外1024字節(jié)。這么接收方共讀了2048字節(jié)。關(guān)于報文流，接收方將得到兩個報文，每個報文1024字節(jié)。而關(guān)于字節(jié)流，報文邊界別被識不。接收方把全部的2048字節(jié)當(dāng)作一具整體，在此差不多體現(xiàn)別出原先有兩個別同的報文的事實。

習(xí)題二

6．假定在地球和一具新月亮之間建立一條100M位/秒的鏈路。從該月亮到地球的距離大約是385000公里，數(shù)據(jù)在鏈路上以光速3×10

8

米/秒傳輸。

（a）計算該鏈路的最小RTT。

解：最小RTT等于2×385000000米÷（3×10

8

米/秒）=2.57秒

（b）使用RTT作為延遲，計算該鏈路的“延遲×帶寬”值。

解：“延遲×帶寬”值等于2.57秒×100M位/秒=257M位≈32M字節(jié)

（c）在（b）中計算的“延遲×帶寬”值的含義是啥？

解：它表示發(fā)送方在收到一具響應(yīng)之前可以發(fā)送的數(shù)據(jù)量。

（d）在月亮上用一具照相機拍取地球的相片，并把它們以數(shù)字形式保存到磁盤上。

假定在地球上的任務(wù)操縱要下載25M字節(jié)的最新圖象，這么，從發(fā)出數(shù)據(jù)請求

到傳送結(jié)束最少要化多少時刻？

解：在圖象能夠開始到達地面之前，至少需要一具RTT。假定僅有帶寬延遲，這么發(fā)送需要的時刻等于25M字節(jié)÷100M位/秒=200M位÷100M位/秒=2秒。因此，直到最終一具圖象位到達地球，總共化的時刻等于2.0+2.57=4.57秒。

2．如圖所示，主機A和B每個都經(jīng)過10M位/秒鏈路連接到交換機S。

在每條鏈路上的傳播延遲基本上20微秒。S是一具存儲轉(zhuǎn)發(fā)設(shè)備，在它接收完一具分組后35微妙開始轉(zhuǎn)發(fā)收到的分組。試計算把10000比特從A發(fā)送到B所需要的總時刻。

（a）作為單個分組

解：每條鏈路的發(fā)送延遲是10000÷10M位/秒=1000微秒

總的傳送時刻等于2×1000+2×20+35=2075微秒。

（b）作為兩個5000位的分組一具緊繼續(xù)另一具發(fā)送

解：當(dāng)作為兩個分組發(fā)送時，下面列出的是各種事件發(fā)生的時刻表：

T=0開始

T=500A完成分組1的發(fā)送，開始發(fā)送分組2

T=520分組1徹底到達S

T=555分組1從S起程前往B

T=1000A結(jié)束了分組2的發(fā)送

T=1055分組2從S起程前往B

T=1075分組2的第1位開始到達B

T=1575分組2的最終1位到達B

其實，從開始發(fā)送到A把第2個分組的最終1位發(fā)送完通過的時刻為2×500微妙，

第1個鏈路延遲20微妙，

500微妙的發(fā)送延遲，

第2個鏈路延遲20微妙，

因此，總的時刻等于2×500微妙+20微妙+35微妙+500微妙+20微妙=1575微妙。

3.如今要在光纖上發(fā)送一具計算機屏幕圖象序列。屏幕大小為480x640象素，每個象素24位，每秒60幅屏幕圖象。咨詢需要多大的帶寬？假定每赫茲調(diào)制一具比特，這么關(guān)于中心波長為1.30μm的波段，那個帶寬所對應(yīng)的波長范圍有多大？

解答:數(shù)據(jù)速率是480x640x24x60bps，即442Mbps

△f=4.42x108

所以，需要442Mbps的帶寬，對應(yīng)的波長范圍是2.5x10

–6

微米。

4.奈魁斯特定理適用于光纖嗎？依然僅適用于銅線？

解答:奈魁斯特定理是一具數(shù)學(xué)性質(zhì)，別涉及技術(shù)處理。該定理講，假如你有一具函數(shù)，它的傅里葉頻譜別包含高于f的正弦或余弦，這么以2f的頻率采樣該函數(shù)，這么你就能夠獵取該函數(shù)所包含的全部信息。所以奈魁斯特定理適用于所有介質(zhì)。

5.假定PSTN的帶寬是3000HZ，典型的信噪功率比是20dB，試確定能夠取得的理論上

最大的信息（數(shù)據(jù)）速率。

解答：

如今，

所以，C=3000×log2(1+100)=19936bps

即能夠取得的理論上最大的信息（數(shù)據(jù)）速率是19936bps。

習(xí)題三

1．假定我們要發(fā)送信息，同時使用CRC多項式x3+1來檢錯

（a）使用多項式長除來確定應(yīng)該發(fā)送的信息塊。

解答：取信息，附加000，并用1001去除，余數(shù)是011

應(yīng)該發(fā)送的信息塊是11001001011

（b）假定信息塊最左邊的比特由于在傳輸鏈路上的噪音而變化，接收方

CRC計算的結(jié)果是啥？接收方是怎么樣懂發(fā)生了錯誤的？

解答：把第1位變反，得到，再用1001去除，得到商，

余數(shù)是10。由于余數(shù)別為零，因此接收方懂發(fā)生了錯誤。

2．假定一具成幀協(xié)議使用比特充填，示出當(dāng)幀包含下列比特序列時在鏈路上發(fā)送的比特序列。

11111111

解答：11111110110

3．在大多數(shù)網(wǎng)絡(luò)中，數(shù)據(jù)鏈路層經(jīng)過請求重傳損壞幀來處理傳輸錯誤。假如一

個幀被損壞的概率為p，在確認(rèn)幀永久不可能被丟失的事情下發(fā)送一幀所需要的平

均傳輸次數(shù)是多少？

解答：一具幀需要傳輸k次的概率pk是開頭k-1次傳輸嘗試失敗的概率p

k-1

乘以第k次傳

輸成功的概率（1-p）。所以，平均傳輸次數(shù)是：

4．思考在一條20公里長的點到點光纖鏈路上運行的ARQ算法

a)假定光在光纖中的傳播速度是2×108米/秒，試計算該鏈路的傳播延遲。

解答：傳播延遲=20×103米÷（2×108米/秒）=100微妙

b)為該ARQ建議一具適當(dāng)?shù)某瑫r值。

解答：往返時刻大約為200微妙。能夠把超時值設(shè)置成該時刻長度的2倍，即

0.4毫秒。取決于在實際的RTT中的變化量額，有時候取小一些的值（但大于0.2毫秒）可能更合理。

c)按照給出的那個超時值實現(xiàn)ARQ算法，為啥該ARQ算法在運行過程

中還也許超時而重傳幀呢？

解答：前面?zhèn)鞑パ舆t的計算沒有思考處理延遲，而在實踐中遠方結(jié)點也許引入處理延遲，即它可能別可以馬上回答。

5．PPP是以HDLC為基礎(chǔ)的，HDLC使用位充填防止在有效載荷內(nèi)間或浮現(xiàn)

的標(biāo)志字節(jié)產(chǎn)生混淆。給出至少一具理由，講明PPP為啥使用字符充填來

代替位充填。

解答：：PPP被明確地設(shè)計成是以軟件形式實現(xiàn)的，而別像HDLC那樣幾乎總是以硬件形

式實現(xiàn)。關(guān)于軟件實現(xiàn)，徹底用字節(jié)操作要比用單個位操作簡單得多。此外，PPP被設(shè)計成

跟調(diào)制解調(diào)器一道使用，而調(diào)制解調(diào)器是以1個字節(jié)為單元而別是以1個比特為單元同意和

發(fā)送數(shù)據(jù)的。

習(xí)題四

1．一大批ALOHA用戶每秒產(chǎn)生50次請求，包括初始請求和重傳的請求。時刻以40毫秒為

單位分槽

（a）首次嘗試的成功率是多少？

解答：在任一幀時內(nèi)生成k幀的概率服從泊松分布

生成0幀的概率為e—G

關(guān)于純ALOHA，發(fā)送一幀的沖突驚險區(qū)為兩個幀時，在兩幀內(nèi)無其它幀發(fā)送的概率為

e—G

．e—G

=e

—2G

關(guān)于分槽ALOHA，由于沖突驚險區(qū)減少為原來的一半，任一幀時內(nèi)無其它幀發(fā)送的概率是

e

—G

。

如今時槽長度為40毫秒，即每秒25個時槽，產(chǎn)生50次請求，因此每個時槽產(chǎn)生兩個請求，G=2。所以，首次嘗試的成功率是

e

-2

=1/e

2

（b）k次沖突后成功的概率是多少？

解答：（1-e

-G

）

k

e—G

=(1-e

-2

)

k

e

-2

=0.135×(1-0.135)

k

=0.135×0.865

k

（c）所需要的發(fā)送嘗試的次數(shù)的期望值是多少？

解答：嘗試k次才干發(fā)送成功的概率（即前k-1次沖突，第k次才成功）為：

pk=e

-G

(1-e

-G

)

k-1

這么每幀傳送次數(shù)的數(shù)學(xué)期望為

2．1982年的以太網(wǎng)規(guī)范允許在任意兩個站之間能夠有長達1500米的同軸電纜、1000米的其它點到點連接線纜和兩個重發(fā)器。每個站或重發(fā)器經(jīng)過最長可達50米的分接電纜連接到

同軸電纜。附表列出了跟每種設(shè)備相關(guān)的典型延遲值（其中的c等于光在真空中的速度3×108米/秒）

條目延遲

同軸電纜傳播速度0.77c

鏈接/分接電纜傳播速度0.65c

重發(fā)器每個大約0.6微秒

收發(fā)器每個大約0.2微秒

由于表中所列出的各種延遲，以比特為單位計量的最壞事情下的來回路程傳播延遲是多少？

解答：單程延遲：

同軸電纜1500米6.49微妙

鏈接線纜1000米5.13微秒

重發(fā)器兩個1.2微妙

收發(fā)器六個（每個重發(fā)器兩個，每個站一具）1.2微妙

尾纜6×50米1.54微妙

累計15.56微妙

來回路程延遲大約31.1微妙或311比特

標(biāo)準(zhǔn)允許的來回路程總延遲是464比特，加上48位的加強碰撞信號剛好等于512位的最小分組尺寸。

3．為啥講以太網(wǎng)幀的長度段關(guān)于相鄰上層（子層）是重要的？

解答：以太網(wǎng)有一具最小幀大小限制（關(guān)于10Mbps是64字節(jié)）；較小的分組必須加襯墊，以填充到最小幀大小。否則，把整個數(shù)據(jù)段的內(nèi)容都遞交給相鄰上層，它將無法區(qū)分實際數(shù)據(jù)和填充。

4．假定以太網(wǎng)的來回路程傳播延遲是46.4微妙。這導(dǎo)致512比特的最小分組尺寸（464位的傳播延遲+48位碰撞增強信號）。

（a）假如延遲時刻保持常數(shù)，當(dāng)信號速率上升到100Mbps時，最小分組大小將是多少？解答：假定仍使用48位的JAM信號，這么最小分組尺寸將是

4640位+48位=4688位=586字節(jié)

（b）這樣大的最小分組尺寸的缺點是啥？

解答：那個分組尺寸比許多高層分組尺寸大得多，產(chǎn)生相當(dāng)數(shù)量的帶寬白費

（c）假如兼容性別是一具咨詢題，怎么樣制定規(guī)范才干允許一具較小的最小分組尺寸？

解答：假如減少最大沖突域直徑，同時其它各種容許量都非常緊張，這么最小分組尺寸能夠比較小。

5．廣播子網(wǎng)的一具缺點是有多個主機試圖拜訪信道時造成的信道容量白費。作為一具簡單例子，假設(shè)把時刻分為離散的時刻片，n臺主機中每一臺主機在每個時刻片內(nèi)試圖占有信道的概率為p。求由于沖突被白費的時刻片的比例。

解答：先區(qū)不n+2種事件。從事件1直到事件n基本上由對應(yīng)的主機試圖使用通道而別發(fā)生碰撞獲得成功的條件形成。這些事件中的每一具的概率都p（1-p）

n-1

閑通道，其概率是（1-p）

n

。事件n+2是一次碰撞。由于這n+2個事件是窮舉的和完備的，

它們概率的和必然是1。所以，碰撞的概率，即白費的時刻片的比率是：

np（1-p）

n-1

-（1-p）

n

習(xí)題五

1．在令牌總線中，假如某站點接到令牌后即崩潰，將會發(fā)生啥事情？802.4協(xié)議是

怎么處理這種事情的？

解答：在一具站將令牌傳出之后，它就觀看它的后繼站是否傳出一幀或者交出令牌。假如二

者均未發(fā)生，這么該站將再次傳出令牌。假如第二次仍失敗，該站就發(fā)送WHO_FOLLOWS

幀，該幀中標(biāo)明了后繼站的地址。當(dāng)崩潰站點的后繼站看到WHO_FOLLOWS幀中給出的

地址是自個兒的前站地址，它就發(fā)送SET_SUCCESSOR幀給出錯站點的前方站點作為響應(yīng)，

聲明自個兒將成為新的后繼站。如此，出錯的站點就從環(huán)中移去。

2．當(dāng)數(shù)據(jù)傳輸速率為5Mbps，且傳播速度為200米/微妙時，令牌環(huán)接口中的一具比

特時延等價于多少米的電纜？

解答：在5Mbps速率下，一具位時等于200毫微妙，在200毫微妙時刻內(nèi)信號能夠傳

播的距離是200×10

-3

×200=40米

所以，令牌環(huán)接口中的一具比特延時等價于40米的電纜。

3．有一具重負(fù)荷的1公里長的10Mbps的令牌環(huán)網(wǎng)，其傳播速率是每微妙200米，50

個站空間上均勻繞環(huán)分布。數(shù)據(jù)幀256位，其中包括32位開銷，確認(rèn)應(yīng)答捎帶在數(shù)據(jù)幀上，

所以是包括在數(shù)據(jù)幀內(nèi)備用的位中，而別占用額外的時刻。令牌是8位。請咨詢，那個環(huán)的

有效數(shù)據(jù)速率比CSMA/CD網(wǎng)高依然低？

解答：從獵取到令牌的時間開始計量，發(fā)送一具分組需要0.1×256=25.6微妙。此外，必須

發(fā)送一具令牌，需要0.1×8=0.8微妙的時刻。令牌必須傳輸20（=1000÷50）米，通過時刻

20÷200=0.1微妙才干到達下一站。此后，下一站又能夠再發(fā)送數(shù)據(jù)幀。所以，我們在26.5（=25.6+0.8+0.1）微妙內(nèi)發(fā)送了224（=256-32）位的數(shù)據(jù)，數(shù)據(jù)速率等于224÷26.5≈8.5Mbps，而10Mbps的CSMA/CD在重負(fù)荷50個站的事情下的有效數(shù)據(jù)率別超過3Mbps。顯然，該

令牌環(huán)網(wǎng)強于以太網(wǎng)的有效帶寬。

4．一具大的FDDI環(huán)有100個站，令牌環(huán)行時刻是40毫秒。令牌保持時刻是10毫秒。

該環(huán)可取得的最大效率是多少？

時刻是40/100，即0.4毫秒。如此一具站能夠發(fā)送10毫秒，繼續(xù)是0.4毫秒的間隙，在此期間令牌挪移到下一站。所以最好事情的效率是：10÷（10+0.4）≈96%，即該環(huán)可取得的最大效率是96%.

5．假定信號在光纖中的延遲是每公里5微妙，試計算以時刻和比特表示的下列FDDI

環(huán)配置的延遲。假定可用的位速率是100Mbps。

（a）2公里環(huán)，帶有20個站；

（b）20公里環(huán)，帶有200個站；

（c）100公里環(huán)，帶有500個站。

解答：設(shè)信號傳播延遲等于Tp，一具站的延遲等于Ts，N表示站的數(shù)目，

這么環(huán)延遲T1=Tp+N×Ts。在這個地方，Ts=0.01微妙

（a）T1=2×5+20×0.01=10.2微妙，或1020比特

（b）T1=20×5+200×0.01=102微妙，或10200比特

（c）T1=100×5+500×0.01=505微妙，或50500比特

需要指出的是，上述值的計就是假定僅使用主環(huán)。假如發(fā)生了故障，將雙環(huán)重構(gòu)成單環(huán)，信號傳播延遲值將加倍。而且，關(guān)于每個雙附接站，站延遲也將加倍。

習(xí)題六

1．下圖表示LAN經(jīng)過網(wǎng)橋互連。請按照圖上所標(biāo)的網(wǎng)橋ID和端口號，利用生成樹算

法求出此網(wǎng)絡(luò)的生成樹。

圖06-15習(xí)題1插圖

解答：

2．思考建立一具CSMA/CD網(wǎng)，電纜長1公里，別使用重發(fā)器，運行速率為1Gbps。電纜中

的信號速度是200000公里/秒。咨詢最小幀長度是多少？

解答：關(guān)于1公里電纜，單程傳播時刻為1÷200000=5×10

-6

秒，即5微妙，來回路程傳

播時刻為2τ=10微妙。為了可以按照CSMA/CD工作，最小幀的發(fā)射時刻別能小于10微妙。以1Gbps速率工作，10微妙能夠發(fā)送的比特數(shù)等于：

所以，最小幀是10000位或1250字節(jié)長。

3．考察下圖中示出的透明橋接器的布局。假定開始時所有的轉(zhuǎn)發(fā)表基本上空的，試給出在下列的傳輸序列之后，橋接器B1-B4中的每一具的轉(zhuǎn)發(fā)表的內(nèi)容：

*A給C傳送

*C給A發(fā)送

*D給C發(fā)送

個端口可標(biāo)識為B1的A端口和B1的B2端口。

解答：當(dāng)A給C傳送時，所有的橋都看到了分組，懂A在哪里。但是，當(dāng)隨后C給A發(fā)送時，分組通過已知路徑B3-B2-B1直截了當(dāng)前往A，B4別懂C在哪里。類似地，當(dāng)D給C發(fā)送時，分組經(jīng)B4傳播到B2后，經(jīng)已知路徑B2-B3直截了當(dāng)前往C，B1別懂D在哪里。因此如今橋接器B1-B4中的每一具的轉(zhuǎn)發(fā)表的內(nèi)容分不為：

橋B1：目的地A--端口A，目的地C—端口B2（無D）

橋B2：目的地A--端口B1，目的地C—端口B3，目的地D—端口B4

橋B3：目的地A--端口B2，目的地C—端口C，目的地D—端口B2

橋B4：目的地A--端口B2，目的地D—端口D（無C）

4．思考圖06-17所示的子網(wǎng)。使用距離向量路由挑選，下列向量剛才被路由器C收到：

來自B：（5，0，8，12，6，2）

來自D：（16，12，6，0，9，10）

來自E：（7，6，3，9，0，4）

路由器C測量得到的到達B、D和E的延時分不等于6、3和5。試咨詢路由器C的新的路由表是啥？請給出所使用的輸出線路和所預(yù)期的延時。

圖06-17習(xí)題4插圖

解答：經(jīng)過B給出（11，6，14，18，12，8）

經(jīng)過D給出（19，15，9，3，12，13）

經(jīng)過E給出（12，11，8，14，5，9）

取到達每一目的地的最小值（C除外）得到：

（11，6，0，3，5，8）

輸出線路是：（B，B，-，D，E，B）

5．圖06-18中每個圓圈代表一具網(wǎng)絡(luò)節(jié)點，每一條線代表一條通信線路，線上的標(biāo)注表示兩個相鄰節(jié)點之間的代價。

圖06-18習(xí)題5插圖

請依照Dijkstra最短通路搜索算法找出A到J的最短路徑。規(guī)定使用直截了當(dāng)在圖上加標(biāo)注的辦法，而且，在答案中只要求：

（1）依次列出每一步的工作節(jié)點

（2）給出從A到J的最短路徑及代價

（3）在原圖上示出最終一步算法完成時圖上每個節(jié)點（除A以外）的標(biāo)注。

解答：(1)每一步的工作節(jié)點如下：

(2)從A到J的最短路徑是ACDEGIJ，