計算機網路結構主要有TCP/IP和OSI參考模型。
網路的拓撲結構是拋開網路物理連接來討論網路系統的連接形式，網路中各站點相互連接的方法和形式稱為網路拓撲。拓撲圖給出網路伺服器、工作站的網路配置和相互間的連接，它的結構主要有星型結構、匯流排結構、樹型結構、網狀結構、蜂窩狀結構、分布式結構等。
星型結構
星型結構是指各工作站以星型方式連接成網。網路有中央節點，其他節點（工作站、伺服器）都與中央節點直接相連，這種結構以中央節點為中心，因此又稱為集中式網路。它具有如下特點：結構簡單，便於管理；控制簡單，便於建網；網路延遲時間較小，傳輸誤差較低。但缺點也是明顯的：成本高、可靠性較低、資源共享能力也較差。
環型結構
環型結構由網路中若干節點通過點到點的鏈路首尾相連形成一個閉合的環，這種結構使公共傳輸電纜組成環型連接，數據在環路中沿著一個方向在各個節點間傳輸，信息從一個節點傳到另一個節點。
環型結構具有如下特點：信息流在網中是沿著固定方向流動的，兩個節點僅有一條道路，故簡化了路徑選擇的控制；環路上各節點都是自舉控制，故控制軟體簡單；由於信息源在環路中是串列地穿過各個節點，當環中節點過多時，勢必影響信息傳輸速率，使網路的響應時間延長；環路是封閉的，不便於擴充；可靠性低，一個節點故障，將會造成全網癱瘓；維護難，對分支節點故障定位較難。
匯流排型結構
匯流排結構是指各工作站和伺服器均掛在一條匯流排上，各工作站地位平等，無中心節點控制，公用匯流排上的信息多以基帶形式串列傳遞，其傳遞方向總是從發送信息的節點開始向兩端擴散，如同廣播電台發射的信息一樣，因此又稱廣播式計算機網路。各節點在接受信息時都進行地址檢查，看是否與自己的工作站地址相符，相符則接收網上的信息。
匯流排型結構的網路特點如下：結構簡單，可擴充性好。當需要增加節點時，只需要在匯流排上增加一個分支介面便可與分支節點相連，當匯流排負載不允許時還可以擴充匯流排；使用的電纜少，且安裝容易；使用的設備相對簡單，可靠性高；維護難，分支節點故障查找難。
分布式結構
分布式結構的網路是將分布在不同地點的計算機通過線路互連起來的一種網路形式，分布式結構的網路具有如下特點：由於採用分散控制，即使整個網路中的某個局部出現故障，也不會影響全網的操作，因而具有很高的可靠性；網中的路徑選擇最短路徑演算法，故網上延遲時間少，傳輸速率高，但控制復雜；各個節點間均可以直接建立數據鏈路，信息流程最短；便於全網范圍內的資源共享。缺點為連接線路用電纜長，造價高；網路管理軟體復雜；報文分組交換、路徑選擇、流向控制復雜；在一般區域網中不採用這種結構。
樹型結構
樹型結構是分級的集中控制式網路，與星型相比，它的通信線路總長度短，成本較低，節點易於擴充，尋找路徑比較方便，但除了葉節點及其相連的線路外，任一節點或其相連的線路故障都會使系統受到影響。
網狀拓撲結構
在網狀拓撲結構中，網路的每台設備之間均有點到點的鏈路連接，這種連接不經濟，只有每個站點都要頻繁發送信息時才使用這種方法。它的安裝也復雜，但系統可靠性高，容錯能力強。有時也稱為分布式結構。
蜂窩拓撲結構
蜂窩拓撲結構是無線區域網中常用的結構。它以無線傳輸介質（微波、衛星、紅外等）點到點和多點傳輸為特徵，是一種無線網，適用於城市網、校園網、企業網。
在計算機網路中還有其他類型的拓撲結構，如匯流排型與星型混合。匯流排型與環型混合連接的網路。在區域網中，使用最多的是匯流排型和星型結構。
OSI七層模型介紹
OSI是一個開放性的通行系統互連參考模型，他是一個定義的非常好的協議規范。OSI模型有7層結構，每層都可以有幾個子層。下面我簡單的介紹一下這7層及其功能。
OSI的7層從上到下分別是
7 應用層
6 表示層
5 會話層
4 傳輸層
3 網路層
2 數據鏈路層
1 物理層
其中高層，既7、6、5、4層定義了應用程序的功能，下面3層，既3、2、1層主要面向通過網路的端到端的數據流。下面我給大家介紹一下這7層的功能：
（1）應用層：與其他計算機進行通訊的一個應用，它是對應應用程序的通信服務的。例如，一個沒有通信功能的字處理程序就不能執行通信的代碼，從事字處理工作的程序員也不關心OSI的第7層。但是，如果添加了一個傳輸文件的選項，那麼字處理器的程序員就需要實現OSI的第7層。示例：telnet，HTTP,FTP,WWW,NFS,SMTP等。
（2）表示層：這一層的主要功能是定義數據格式及加密。例如，FTP允許你選擇以二進制或ASII格式傳輸。如果選擇二進制，那麼發送方和接收方不改變文件的內容。如果選擇ASII格式，發送方將把文本從發送方的字元集轉換成標準的ASII後發送數據。在接收方將標準的ASII轉換成接收方計算機的字元集。示例：加密，ASII等。
（3）會話層：他定義了如何開始、控制和結束一個會話，包括對多個雙向小時的控制和管理，以便在只完成連續消息的一部分時可以通知應用，從而使表示層看到的數據是連續的，在某些情況下，如果表示層收到了所有的數據，則用數據代表表示層。示例：RPC，SQL等。
（4）傳輸層：這層的功能包括是否選擇差錯恢復協議還是無差錯恢復協議，及在同一主機上對不同應用的數據流的輸入進行復用，還包括對收到的順序不對的數據包的重新排序功能。示例：TCP，UDP，SPX。
（5）網路層：這層對端到端的包傳輸進行定義，他定義了能夠標識所有結點的邏輯地址，還定義了路由實現的方式和學習的方式。為了適應最大傳輸單元長度小於包長度的傳輸介質，網路層還定義了如何將一個包分解成更小的包的分段方法。示例：IP,IPX等。
（6）數據鏈路層：他定義了在單個鏈路上如何傳輸數據。這些協議與被討論的歌種介質有關。示例：ATM，FDDI等。
（7）物理層：OSI的物理層規范是有關傳輸介質的特性標准，這些規范通常也參考了其他組織制定的標准。連接頭、針、針的使用、電流、電流、編碼及光調制等都屬於各種物理層規范中的內容。物理層常用多個規范完成對所有細節的定義。示例：Rj45，802.3等。
⑵ 計算機網路自學筆記：選路演算法
網路層必須確定從發送方到接收方分組所經過的路徑。選路就是在網路中的路由器里的給某個數據報確定好路徑(即路由)。
一 台主機通常直接與一台路由器相連接，該路由器即為該主機的默認路由器，又稱為該主機的默認網關。 每當某主機向外部網路發送一個分組時，該分組都被傳送給它的默認網關。
如果將源主機的默認網關稱為源路由器,把目的主機的默認網關稱為目的路由器。為一個分組從源主機到目的主機選路的問題於 是可歸結為從源路由器到目的路由器的選路問題。
選路演算法的目標很簡單:給定一組路由器以及連接路由器的鏈路，選路演算法要找到一條從源路由器到目的路由器的最好路徑，通常一條好路徑是指具有最低費用的路徑。
圖 G=(N，E)是一個 N 個節點和 E 條邊的集合，其中每條邊是來自 N 的一對節點。在網 絡選路的環境中，節點表示路由器，這是做出分組轉發決定的節點，連接節點的邊表示路由 器之間的物理鏈路。
一條邊有一個值表示它的費用。通常一條邊的費用可反映出對應鏈路的物理長度、鏈路速度或與該鏈路相關的費用。
對於 E 中的任一條邊(xy)可以用 c(xy )表示節點 x 和 y 間邊的費用。一般考慮的都是無向 圖，因此邊(xy)與邊(y x)是相同的並且開銷相等。節點 y 也被稱為節點 x 的鄰居。
在圖中為各條邊指派了費用後，選路演算法的目標自然是找出從源到目的間的最低費用路徑。圖 G=(N，E)中的一條路徑(Path)是一個節點的序列，使得每一對以(x1,x2)， (x2,x3)，…，是 E 中的邊。路徑的費用是沿著路徑所有邊費用的總和。
從廣義上來說，我們對 選路演算法分類的一種方法就是根據該演算法是全局性還是分布式來區分的。
.全局選路演算法： 用完整的、全局性的網路信息來計算從源到目的之間的最低費用路徑。
實際上， 具有全局狀態信息的演算法常被稱作鏈路狀態 LS 演算法， 因為該演算法必須知道網路中每條鏈路的費用。
.分布式選路演算法： 以迭代的、分布式的方式計算出最低費用路徑。通過迭代計算並與相鄰節點交換信息，逐漸計算出到達某目的節點或一組目的節點的最低費用路徑。
DV 演算法是分布式選路演算法， 因為每個節點維護到網路中的所有其他節點的費用(距離)估計的矢量。
選路演算法的第二種廣義分類方法是根據演算法是靜態的還是動態的來分類。
一： 鏈路狀態選路演算法 LS
在鏈路狀態演算法中，通過讓每個節點向所有其他路由器廣播鏈路狀態分組， 每個鏈路狀態分組包含它所連接的鏈路的特徵和費用， 從而網路中每個節點都建立了關於整個網路的拓撲。
Dijkstra 演算法計算從源節點到網路中所有其他節點的最低費用路徑.
Dijkstra 演算法是迭代演算法，經演算法的第 k 次迭代後，可知道到 k 個目的節點的最低費用路徑。
定義下列記號:
D(V)隨著演算法進行本次迭代，從源節點到目的節點的最低費用路徑的費用。
P(v)從源節點到目的節點 v 沿著當前最低費用路徑的前一節點(，的鄰居)。
N`節點子集；如果從源節點到目的節點 v 的最低費用路徑已找到，那麼 v 在 N`中。
Dijkstra 全局選路演算法由一個初始化步驟和循環組成。循環執行的次數與網路中的節點個數相同。在結束時，演算法會計算出從源節點 u 到網路中每個其他節點的最短路徑。
考慮圖中的網路，計算從 u 到所有可能目的地的最低費用路徑。
.在初始化階段 ，從 u 到與其直接相連的鄰居 v、x、w 的當前已知最低費用路徑分別初始化為 2，1 和 5。到 y 與 z 的費用被設為無窮大，因為它們不直接與 u 連接。
.在第一次迭代時， 需要檢查那些還未加到集合 N`中的節點，找出在前一次迭代結束時具有最低費用的節點。那個節點是 x 其費用是 1，因此 x 被加到集合 N`中。然後更新所有節點的 D(v)，產生下表中第 2 行(步驟)所示的結果。到 v 的路徑費用未變。經過節點 x 到 w 的 路徑的費用被確定為 4。因此沿從 u 開始的最短路徑到 w 的前一個節點被設為 x。類似地， 到 y 經過 x 的費用被計算為 2，且該表項也被更新。
.在第二次迭代時 ，節點 v 與 y 被發現具有最低費用路徑 2。任意選擇將 y 加到集合 N` 中，使得 N』中含有 u、x 和 y。通過更新，產生如表中第 3 行所示的結果。
.以此類推…
當 LS 演算法結束時，對於每個節點都得到從源節點沿著它的最低費用路徑的前繼節點， 對於每個前繼節點，又有它的前繼節點，按照此方式可以構建從源節點到所有目的節點的完 整路徑。
根據從 u 出發的最短路徑，可以構建一個節點(如節點 u)的轉發表。
二 距離矢量選路演算法 DV
LS 演算法是一種使用全局信息的演算法，而距離矢量演算法是一種迭代的、非同步的和分布式的演算法。
Bellman-Ford 方程：
設 dx(y)是從節點 x 到節點 y 的最低費用路徑的費用，則有 dx(y) = min {c(x,v) + dv(y) }
PS： 方程中的 min，是指取遍 x 的所有鄰居。
Bellman-Ford 方程含義相當直觀，意思是從 x 節點出發到 y 的最低費用路徑肯定經過 x 的某個鄰居，而且 x 到這個鄰居的費用加上這個鄰居到達目的節點 y 費用之和在所有路徑 中其總費用是最小的。 實際上，從 x 到 v 遍歷之後，如果取從 v 到 y 的最低費用路徑，該路 徑費用將是 c(x,v)+ dv(y)。因此必須從遍歷某些鄰居 v 開始，從 x 到 y 的最低費用是對所有鄰 居的 c(x,v)+dv(y)的最小值。
在該 DV 演算法中，當節點 x 看到它的直接相連的鏈路費用變化，或從某個鄰居接收到一 個距離矢量的更新時，就根據 Bellman-Ford 方程更新其距離矢量表。
三 LS 與 DV 選路演算法的比較
DV 和 LS 演算法採用不同的方法來解決計算選路問題。
在 DV 演算法中，每個節點僅與它的直接相連鄰居交換信息，但它為它的鄰居提供了從其 自己到網路中(它所知道的)所有其他節點的最低費用估計。
在 LS 演算法中，每個節點(經廣播)與所有其他節點交換信息，但它僅告訴它們與它直接 相連鏈路的費用。
·報文復雜性：
LS 演算法要求每個節點都知道網路中每條鏈路的費用，需要發送 O(nE)個消息。
DV 演算法要求在每次迭代時，在兩個直接相連鄰居之間交換報文，演算法收斂所需的時間 依賴於許多因素。當鏈路費用改變時，DV 演算法僅當在會導致該節點的最低費用路徑發生改 變時，才傳播已改變的鏈路費用。
·收效速度：
DV演算法收斂較慢，且在收斂時會遇到選路環路。DV演算法還會遭受到計數到無窮的問題。
•健壯性： 在 LS 演算法中，如果一台路由器發生故障、或受到破壞，路由器會向其連接的鏈路廣播 不正確費用，導致整個網路的錯誤。
在 Dv 演算法下， 每次迭代時，其中一個節點的計算結果會傳遞給它的鄰居，然後在下次迭代時再間接地傳遞給鄰居的鄰居。在這種情況下，DV 演算法中一個不正確的計算結果也會擴散到整個網路。
四.層次選路
兩個原因導致層次的選路策略：
•規模： 隨著路由器數目增長，選路信息的計算、存儲及通信的開銷逐漸增高。
•管理自治： 一般來說，一個單位都會要求按自己的意願運行路由器(如運行其選擇的某 種選路演算法)，或對外部隱藏其內部網路的細節。
層次的選路策略是通過將路由器劃分成自治系統 AS 來實施的。
每個 AS 由一組通常在相同管理控制下的路由器組成(例如由相同的 ISP 運營或屬於相同 的公司網路)。在相同的 AS 內的路由器都全部運行同樣的選路演算法。
在一個自治系統內運行的選路演算法叫做自治系統內部選路協議。 在一個 AS 邊緣的一台 或多台路由器，來負責向本 AS 之外的目的地轉發分組，這些路由器被稱為網關路由器
在各 AS 之間，AS 運行相同的自治系統間選路協議。
⑶ 計算機網路的問題，麻煩高人幫我詳細解答
對於第一個問題：用距離除以速度就是每一個bit的傳輸時間即：
100Km/(2*10^8m/s)=0.5ms，所以傳播延遲為：100*0.5ms=50ms
要使得發送時延等於傳播時延，那麼就有100/C=0.5ms
所以，發送時延大概為：2000kbps
對於第二問：有源樹是以多播源作為有源樹的根，有源樹的分支形成網路到達目的地址的分布樹，有源樹是以最短路徑貫穿網路
共享樹是以多播源中某些可供選擇的多播路由中的一個作為作為共享樹的一個公共根，即匯合點
對於問題三：沒有考慮過哈，主要是沒有這方面的資料。
對於第四問： TCP序列號為32bit
則位元組流發送數為2^32位元組時TCP序列號回繞
2^32Byte=4GB數據
40Gbps管道=5GB管道
則回繞時間為 4GB/5GB=0.8秒
所以0.8秒便出現回繞
使用擴展的TCP選項時標解決回繞問題
設時標的時鍾頻率為1KHZ, 則每秒時鍾滴答10^3次
對於32bit的擴展選項而言
一共有2^32個數字以供時鍾滴答
則需要時間為2^32/10^3 秒
簡單的估算為2^32/2^10 秒 (2^10=1024,約為1000)
約為4*10^6秒 大約46天回繞一次
對於第五問：不能
網路擁塞指的是單位時間內數據流量超過伺服器或線路的承受能力，從而造成的擁 塞。解決辦法可以增加伺服器處理能力和處理速度，增加帶寬。
網路資源是個泛指，網路上的信息，資料以及硬體軟體等等都可以叫網路資源，與網路擁塞沒啥聯系
對於第六問：由於UDP和TCP的機制不同，有一下幾個原因：
1.最低開銷。
2.在最大數據從傳輸速率開始發送。
3.不重復請求，所以就沒有重傳（一個單一的數據包丟失在一個的實時應用中並不重要）。
4.低處理時間(low processing time)。不需要緩沖(No buffers)。
與TCP不同，UDP並不提供對IP協議的可靠機制、流控制以及錯誤恢復功能等。由於UDP 比較簡單，UDP頭包含很少的位元組，比TCP負載消耗少。
對於第七問：數字簽名可以用來驗證文檔的真實性和完整性，數字簽名使用強大的加密技術和公鑰基礎結構，以更好地保證文檔的真實性、完整性和受認可性。
對於第八問：二層交換技術＋三層轉發技術。它解決了區域網中網段劃分之後，網段中子網必須依賴路由器進行管理的局面，解決了傳統路由器低速、復雜所造成的網路瓶頸問題。
傳統的交換技術是在OSI網路標准模型中的第二層――數據鏈路層進行操作的，而三層交換技術是在網路模型中的第三層實現了數據包的高速轉發。
原理如下：假設兩個使用IP協議的站點A、B通過第三層交換機進行通信，發送站點A在開始發送時，把自己的IP地址與B站的IP地址比較，判斷B站是否與自己在同一子網內。若目的站B與發送站A在同一子網內，則進行二層的轉發。若兩個站點不在同一子網內，如發送站A要與目的站B通信，發送站A要向「預設網關」發出ARP(地址解析)封包，而「預設網關」的IP地址其實是三層交換機的三層交換模塊。當發送站A對「預設網關」的IP地址廣播出一個ARP請求時，如果三層交換模塊在以前的通信過程中已經知道B站的MAC地址，則向發送站A回復B的MAC地址。否則三層交換模塊根據路由信息向B站廣播一個ARP請求，B站得到此ARP請求後向三層交換模塊回復其MAC地址，三層交換模塊保存此地址並回復給發送站A,同時將B站的MAC地址發送到二層交換引擎的MAC地址表中。從這以後，當A向B發送的數據包便全部交給二層交換處理，信息得以高速交換。由於僅僅在路由過程中才需要三層處理，絕大部分數據都通過二層交換轉發，因此三層交換機的速度很快，接近二層交換機的速度，同時比相同路由器的價格低很多。
對於第九問：
P2P：意思是在你自己下載的同時，自己的電腦還要繼續做主機上傳，這種下載方式，人越多速度越快，但缺點是對你的硬碟損傷比較大（在寫的同時還要讀），還有就是對你內存佔用較多，影響整機速度！
C/S結構軟體（即客戶機/伺服器模式）：分為客戶機和伺服器兩層，客戶機不是毫無運算能力的輸入、輸出設備，而是具有了一定的數據處理和數據存儲能力，通過把應用軟體的計算和數據合理地分配在客戶機和伺服器兩端，可以有效地降低網路通信量和伺服器運算量。由於伺服器連接個數和數據通信量的限制，這種結構的軟體適於在用戶數目不多的區域網內使用。
B/S(瀏覽器/伺服器模式，即Browser/Server)是隨著Internet技術的興起，對C/S結構的一種改進。在這種結構下，軟體應用的業務邏輯完全在應用伺服器端實現，用戶表現完全在Web伺服器實現，客戶端只需要瀏覽器即可進行業務處理，是一種全新的軟體系統構造技術。這種結構更成為當今應用軟體的首選體系結構。e通管理系列產品即屬於此類結構。
其實對於問題十而言：可以使NAT轉換技術，將私有地址轉換進入網路，這樣方便的多，而對於以上問題而言，這個題就是使用CIDR技術進行求解就是了，計算還是比較簡單，就是計算過程比較多。
A：市場部一直是16個 ，工程部開始有5個，一周增加一個，一年增加54個（一年好像是54個星期，我記不太清楚了）再乘以7，54*7+5=383個
至於銷售部，地址分配都是考慮到以後發展的，所以根據發展的程度來決定地址空間的冗餘度，算出7年後的總地址數N，2的M次方-2=N 求出M，M就是主機位，結果也就出來了
B：維持的時間，用函數簡單計算就是了， 如果用完了，有兩種辦法：1 再去申請 2 使用NAT技術，3 因為得到的是B類地址，使用CIDR在重新分配就是了。
C：這個問就像最開始一樣的，不用共有地址，就是內部使用私有地址，使用NAT技術就是了。
⑷ 計算機網路的最短路徑演算法有哪些對應哪些協議
用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：
確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題：求圖中所有的最短路徑。
Floyd
求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度O(V^3)。
Floyd-Warshall演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。
Floyd-Warshall演算法的時間復雜度為O(N^3)，空間復雜度為O(N^2)。
Floyd-Warshall的原理是動態規劃：
設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。
若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；
若最短路徑不經過點k，則Di,j,k = Di,j,k-1。
因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。
在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。
Floyd-Warshall演算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;
其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連接。
Dijkstra
求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）,可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。
當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
Bellman-Ford
求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間復雜度O（VE）。
Bellman-Ford演算法是求解單源最短路徑問題的一種演算法。
單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。
與Dijkstra演算法不同的是，在Bellman-Ford演算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環
路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而Bellman-Ford演算法具有分辨這種負環路的能力。
SPFA
是Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k< 與Bellman-ford演算法類似，SPFA演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA演算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
SPFA演算法可以用於存在負數邊權的圖，這與dijkstra演算法是不同的。
與Dijkstra演算法與Bellman-ford演算法都不同，SPFA的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為Bellman-ford演算法，其時間復雜度為O(VE)。
SPFA演算法在負邊權圖上可以完全取代Bellman-ford演算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法，以及它的使用堆優化的版本。通常的SPFA。
⑸ 計算機網路中分組鏈路的數據傳輸速率是100Mbit/s 求傳輸時間
分組大小為1000B，頭大小為20B，因此每個分組最大載荷980B。
因此980000B的文件需要1000個1000B的分組才能傳輸完成，傳輸時間為1000*1000*8÷100M = 80ms
H1到H2之間的最短路徑為3個鏈路，分組延時為1000*8÷100M = 0.08ms，因此鏈路物理延遲為0.08×3 = 0.24ms
綜上，從H1開始發送首個比特到H2接收完最後一個比特，總共至少需要80.24ms。
⑹ 求解兩道計算機網路技術題目
第二題：
（1）每個分組大小1000b，頭100b，顯然每個分組的數據部分是1000-100=900b，而總數據大小是9000b，故需要9000/900=10個分組
（2）總的發送時延=總分組大小/數據傳輸速度=1000b*10個/10Mbps=1000微秒
（3）如圖所示，題目說了各個線路的傳輸速率都一樣是10Mbps，所以不用什麼迪傑斯特拉演算法求最短路徑，直接數路由器的個數就行了，最少的路由數當然是三個，就是最下面這條嘛
（4）分組在各個路由器內部的排隊處理時延是100微秒，那麼每個分組的時延就是100/10=10微秒
（5）這種分組交換的時延計算問題其實可以這樣看，先將總數據按電路交換算發送時延，再加上最後一個分組按報文交換計算的轉發時延，最後再加上一些傳播、排隊、處理等的時延即可。
總的發送時延就是（2）的1000微秒，最後一個分組第一次的發送時延已經包括在總發送時延裡面了，故只需計算它的轉發時延即可，轉發時延=（1000b/10Mbps）*3=300微秒，故總的發送加轉發時延是1000+300=1300微秒，然後總排隊處理時延=4*100=400微秒，總傳播時延=4*10=40微秒，故從H1發送到H2接收，總時延是1300+400+40=1740微秒
如果答案不對，那有可能是排隊處理時延指的是每個分組，也就是總排隊處理時延要再乘10，最後結果是1300+4000+40=5340微秒，相應的（4）就改為100微秒
大體的過程就是如此，其實出題人很仁慈了，一個一個問號帶你做，真正的考試應該沒有（1）（2）（3）（4）問，直接就是（5）求從發送到接收的總時延。