路由器的路由演算法距離矢量演算法和最短路徑演算法。距離矢量由跳數決定，跳數值越小。路徑越短
最短路徑演算法由生成樹協議根據鏈路狀態決定。
B. 幾道計算機網路小題
D C 錯 對
RIP協議的全稱是路由信息協議（Routing Information Protocol），它是一種內部網關協議（IGP），用於一個自治系統（AS）內的路由信息的傳遞。RIP協議是基於距離矢量演算法（Distance Vector Algorithms）的，它使用「跳數」，即metric來衡量到達目標地址的路由距離。
C. 計算機網路模擬題1
IP包頭長度最小24位元組。所以載荷長度為800-24=776位元組。
D. 距離矢量路由演算法 （計算機網路題
通過B到個點的距離為：(11，6，14，18，12，8)，因為B到A的距離為5，C到B的距離為6所以C到A的距離更新為5+6=11，C到B的距離沒變為6，C通過B到C的距離為6+8=14，C通過B到D的距離為6+12=18，C通過B到E距離6+6=12，C通過B到F距離為6+2=8。
通過D到個點的距離為：(19，15，9，3，12，13)，通過D到A的距離為3+16=19，通過D到B的距離為3+12=15，通過D到C的距離為6+3=9，通過D到D的距離為3，通過D到E的距離為3+9=12，通過D到F的距離為3+10=13。
通過E到個點的距離為：(12，11，8，14，5，9)，通過E到A的距離為5+7=12，通過E到B的距離為5+6=11，通過E到C的距離為5+3=8，通過E到D的距離為5+9=14，通過E到Eden距離為5，通過E到F的距離為9。
取到達每一目的地的最小值(C除外)得到: (11， 6，0，3, 5，8)就得出了新的路由表。輸出的路線輸出線路是: (B,，B， -，D，E， B)。
(4)計算機網路的距離矢量演算法擴展閱讀：
路由演算法的度量標准：
路由演算法使用了許多種不同的度量標准去決定最佳路徑。復雜的路由演算法可能採用多種度量來選擇路由，通過一定的加權運算，將它們合並為單個的復合度量、再填入路由表中，作為尋徑的標准。
通常所使用的度量有：路徑長度、可靠性、時延、帶寬、負載、通信成本等。
路徑長度：
路徑長度是最常用的路由。一些路由協議允許網管給每個網路連接人工賦以代價值，這種情況下，路由長度是所經過各個鏈接的代價總和。
可靠性：
可靠性，在路由演算法中指網路連接的可依賴性（通常以位誤率描述），有些網路連接可能比其它的失效更多，網路失效後，一些網路連接可能比其它的更易或更快修復。
路由延遲：
路由延遲指分組從源通過網路到達目的所花時間。很多因素影響到延遲，包括中間的網路連接的帶寬、經過的每個路由器的埠隊列、所有中間網路連接的擁塞程度以及物理距離。
帶寬
帶寬指連接可用的流通容量。在其它所有條件都相等時，10Mbps的乙太網鏈接比64kbps的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量，但是通過具有較大帶寬的鏈接做路由不一定比經過較慢鏈接路由更好。
負載：
負載指網路資源，如路由器的繁忙程度。負載可以用很多方面計算，包括CPU使用情況和每秒處理分組數。持續地監視這些參數本身也是很耗費資源的。
通信代價：
通信代價是另一種重要的metric，尤其是有一些公司可能關心運作費用甚於關心性能。即使線路延遲可能較長，他們也寧願通過自己的線路發送數據而不採用昂貴的公用線路。
參考資料來源：網路-路由演算法
E. 計算機網路選擇7
69 .A70.B6.B71.D72.C73.B74。B75.A76.B77.A78.B79.B80.B
F. 計算機網路中的網路要素包括
．計算機網路的協議三要素
答：三要素是：1，語法：關於諸如數據格式及信號電平等的規定；2，語義：關於協議動作和差錯處理等控制信息；3，定時：包含速率匹配和排序等。
你還可以了解更多啊！
計算機網路
1． 關於計算機網路的定義。
答：廣義的觀點：計算機技術與通信技術相結合，實現遠程信息處理或進一步達到資源共享的系統；資源共享的觀點：以能夠相互共享資源的方式連接起來，並且各自具有獨立功能的計算機系統的集合；對用戶透明的觀點：存在一個能為用戶自動管理資源的網路操作系統，由它來調用完成用戶任務所需要的資源，而整個網路像一個大的計算機系統一樣對用戶是透明的，實際上這種觀點描述的是一個分布式系統。
2． 計算機網路的拓樸結構。
答：計算機網路採用拓樸學的研究方法，將網路中的設備定義為結點，把兩個設備之間的連接線路定義為鏈路。計算機網路也是由一組結點和鏈路組成的的幾何圖形，這就是拓樸結構。
分類：按信道類型分，分為點---點線路通信子網和廣播信道的通信子網。採用點——點連線的通信子網的基本結構有四類：星狀、環狀、樹狀和網狀；廣播信道通子網有匯流排狀、環狀和無線狀。
3． 計算機網路的體系結構
答：將計算機網路的層次結構模型和分層協議的集合定義為計算機網路體系結構。
4．計算機網路的協議三要素
答：三要素是：1，語法：關於諸如數據格式及信號電平等的規定；2，語義：關於協議動作和差錯處理等控制信息；3，定時：包含速率匹配和排序等。
5．OSI七層協議體系結構和各級的主要作用
答：七層指：由低到高，依次是物理層，數據鏈路層，網路層，傳輸層，會話層，表示層和應用層。各層作用分別是：
物理層：向上與數據鏈路層相連，向下直接連接傳輸介質。提供一些建立、維持和釋放物理連接的方法，以便能在兩個或多個數據鏈路實體間進行數據位流的傳輸。
數據鏈路層：通過差錯控制、流量控制等，將不可靠的物理傳輸信道變成無差錯的可靠的數據鏈路。將數據組成適合正確傳輸的幀形式的數據單元，對網路層屏蔽物理層的特性和差異，使高層協議不必考慮物理傳輸介質的可靠性問題。
網路層：決定數據在通信子網中的傳送路徑，控制通信子網中的數據流量並防止擁塞等，提供建立、維護和終止網路連接的手段。網路層是通信子網的最高層。
傳輸層：為源主機到目的主機提供可靠的、有效的數據傳輸，這種傳輸與網路無關，傳輸層是獨立於物理網路的。其上層協議不必了解實際網路，就可將數據安全可靠地傳送到目的地。
會話層：建立、維護和同步進行通信的高層之間的對話。服務主要是：協調應用程序之間的連接建立和中斷；為數據交互提供同步點；協調通信雙方誰可在何時發送數據；確保數據交換在會話關閉之前完成等。
表示層：把源端機器的數據編碼成適合於傳輸的比特序列，傳送到目的端後再進行解碼，在保持數據含義不變的條件下，轉換成用戶所理解的形式。
應用層：為用戶的應用進程訪問OSI環境提供服務。
6．TCP/IP協議體系結構
答：TCP/IP是一個協議系列，目前已飲食了100多個協議，用於將各種計算機和數據通信設備組成計算機網路。
TCP/IP協議具有如下特點：1，協議標准具有開放性，其獨立於特定的計算機硬體與操作系統，可以免費使用；2，統一分配網路地址，使得整個TCP/IP設備在網路中都具有惟一的IP地址。
分層：應用層（SMTP, DNS, NFS, FTP, Telnet, Others）、傳輸層（TCP,UDP）、互聯層（IP，ICMP, ARP, RARP）、主機——網路層(Ethernet, ARPANET, PDN ,Others)。
傳輸控制協議TCP：定義了兩台計算機之間進行可靠數據傳輸所交換的數據和確認信息的格式，以及計算機為了確保數據的正確到達而採取的措施。
IP協議：
7．計算機網路常用的傳輸介質及光纖傳輸的類型與特點
答：有：1，有線介質，包括雙絞線，同軸電纜，光纖；2，無線介質，包括無線電傳輸系統，紅外線，微波。
雙絞線：將兩根相互絕緣的導體按一定的規格將它們纏繞在一起製成。
同軸電纜：由兩個同心圓導中間填充絕緣材料製成。
8．計算機網路的交換技術種類和各自的特點
答：數據交換的種類有：線路交換，報文交換，分組交換（虛電路，數據報），快速交換（ATM（非同步傳輸模式），FR（幀中繼））。
線路交換：在一對需要進行通信的設備（結點）之間提供一條暫的專用的傳輸通道。工作步驟：線路建立，數據通信，電路拆除，釋放相關資源。
報文交換特點：1，在源與目的結點之間無須建立專用通道，對網路的故障適應能力較強；2，沒有建立和拆除電路的時間延遲；3，線路利用率較高，可以進行速率上的調整；4，可靠性較高；5，每個節點對報文進行全面的處理，如果傳輸出錯，要重發整個報文。
分組交換（packet switching）：傳輸的信息是報文分組，將一個長的報文分割成若干個分組來傳輸。
高速交換：ATM（非同步傳輸模式）：把線路交換跟分組交換相結合。以固定長度（53位元組：信元頭5位元組，正文48位元組）。FR（幀中繼）：採用永久虛電路，只要接收完幀的目的地址（不是指向本結點就立即轉發幀）若傳輸出錯，則給下游結點發送錯誤指示，要它終止接收，並要求上游重發該幀。
9．以數據報為例敘述交換技術的工作過程
10．CSMA/CD匯流排型網路的拓樸結構，幀結構及其基本工作過程
CSMA/CD（Carrier sense Multiple Access with Collision Detection）帶有沖突檢測的載波偵聽多路訪問。
拓樸結構：？
11．令牌環網的拓樸結構，幀結構及其基本工作過程
12．計算機網路流量控制的目的和流量控制的級別
目的：1，防止網路因過載而引起吞吐量下降和延時的增加；2，減少擁塞，避免死鎖；3，在互相競爭的用戶之間公平合理地分配資源。
四種級別：1，相鄰結點間的流量控制，2，源結點和目的結點間的流量控制；3，主機與源結點間的流量控制；4，源主機與目的主機間的流量控制。
13．關於源路由網橋的概念和工作原理（P102）
源路由網橋（IEEE802。5工作組選用的網橋，面向令牌環網）：是指源站點要提供偵傳送的路由信息，該路由信息（Routing Information）設置在該幀的頭部，用於標識幀的傳輸路徑（面向連接的網橋）。
工作原理：源站要向目的站通信前，必須尋找通向目的站的路徑（實際上是建立連接的過程：源站首先向全網廣播一個「探測幀」，該幀每經過一個網橋，網橋把自己相關路由信息寫入該探測幀，為該到達目的站時，該數據包就記錄下一張它所經過的路徑圖（路由表）。目的站會使這個探測幀返回（實際由目的站發出一個應答幀）當源站接收到應答幀時，則可以說連接已建立）。
14．關於透明網橋的概念和工作原理（P99）
所謂透明網橋是指網橋的操作過程對其埠上連接的網段上的工作站是「透明的」，換句話說，工作站用戶並不知道網橋的存在。
15．路由器的基本工作過程及其作用
基本工作過程：
A， 路由器工作在網路層，它的傳輸單位是分組（packet），又稱數據包
B， 當路由器接收到一個包時，首先進行拆包，把數據鏈路層的信息去掉，讀取網路層的信息
C， 根據包的目的地址（指向）進行：本地提交（本網是目的結點所在網路）；分組轉發（選擇轉發路由）
D，數據安全性檢查（轉發檢驗）
E， 通過安全檢查後，則進行打包，（封裝）加入數據鏈路層的信息，轉發該包。
基本功能：
1， 協議轉換
2， 路由選擇
3， 支持多協議的路由選擇
4， 流量控制
5， 分組的分段與組裝
6， 網路管理功能
（未完成）16．路由選擇演算法的分類和理想路由選擇演算法應具有的特點
路由演算法有：距離矢量演算法和鏈路狀態演算法。
距離矢量演算法：以某一參考點到達目的結點的距離作為度量的演算法。這里的距離指該路徑上所經歷的最少網關（也指路由器）數。
鏈路狀態演算法：實際上是一種「最短路徑優先」的演算法。
特點：？
17．距離向量演算法和RIP的工作過程(p110)
距離向量演算法的基本思想：以某一參考點到目的結點的距離作為演算法的度量。
RIP（routing Information Protocol）路由信息協議工作過程：1，初始化（啟動RIP協議）；2，路由表交換路由信息；3，路由表更新（最知線路優先）。（P113）
18．路由器的主機名和埠配置使用方法
配置主機名（路由器）：每台路由器主機的預設名Router。假設把它配置為路由器R2則輸入命令：
router (config) #host name Router (R2)
顯示：Router R2 (config) #
埠配置（埠地址配置）：
① Router R2 (config) # interface eithernet 0
② Router R2 (config-if) # ip address 200.111.50.1 255.255.255.0
配置埠的IP地址：200.111.50.1
相應的子網掩碼：255.255.255.0
③ Router R2 (config ) # interface serial 0 (0是串列口)
④ Router R2 (config-if)# ip address 128.120.1.1 255.255.255.0
19．奈奎斯特和香農定律原理
（離散信號的信道容量）奈奎斯特定律：C = 2 F log2 L (bps) 每秒的信道容量，信道的最大傳輸速率
C：信道容量。 F：帶寬。 L：符號的離散取值。
（連續信號的信道容量）香農定律：C = F log2 (1+S/N)
S:通過的信號平均功率。 N：雜訊（干擾信號）的功率。所謂雜訊是指干擾信號（雜訊）在所有頻率上的強度都一樣。 S/N：採用信噪比來代替。 SNR 其單位是分貝。DB
分貝值 = 10 log10 (S/N) 分貝值是可測量的。則可利用分貝值得到S/N。
20．計算機網路中常用的編碼技術
（1） 單極性不歸零編碼（NRZ）
（2） 曼徹斯特編碼（Manchester Encoding）
（3） 差分曼徹斯特編碼
21．畫圖說明頻移鍵控法的工作原理
22．PCM技術的基本工作步驟
1， 取樣：按照一定的時間間隔采樣測量模擬信號幅值
2， 量化：將取樣點測量的信號幅值分級取整
3， 編碼：將量化的結果（整數據）用二進制數表示出來
23．非同步傳輸的編碼結構
也叫「起/停方式」：每傳送1個字元（5bit/8bit）都在字元前面加入一位開始位（「0」表示使用停電平表示傳送開始），而在代碼校驗（奇/偶）後面跟隨停止位（1位，3/2位或2位，用「1」高電平表示，代表字元傳輸結束）
以ASCII碼的A字元為例（11位非同步碼結構）
A字元：41H = 1000001 編碼後：01000001111
24．HDLC的幀結構和基於比特流的傳輸控制流程規程的主要特性
HDLC(High Data Link Control)高級數據鏈路控制：基於比特傳輸的控制規程。主要特徵如下：
① 通信方式：全雙工
② 差錯控制：循環冗餘碼（CRC）
③ 同步方式：同步
④ 電碼：隨機碼（任意二進制編碼）
⑤ 信息長度：可變區
⑥ 速率：2400bps以上
⑦ 發關方式：連續發送，即發送方送出一個信息幀後，不等接收方的應答，則繼續發關隨後的幀，接收方的應答信號是利用全雙工的另一信道在它發送給發送方的信息幀的控制欄位中夾帶回「已收到某編號的信息幀」（期待接收某個編號的幀）這表明此號幀以前的信息幀已正確接收。如果發現傳輸出錯，則請求重傳該號幀及其隨後的幀。
HDLC的幀結構：
F
A
C
I
FCS
F
同步標志（01111110） 地址 控制欄位 正文 循環冗餘碼 標志
25．計算機網路中使用的循環冗餘碼校驗的工作原理
26．多路復用的基本思想和種類
多路復用原理：就是讓一條線路復用成多個子信道來使用
種類有：
1， 頻分多路復用（FDM）：分割線路的帶寬，形成多個子信道（頻度）
2， 同步時分多路復用（TDM）：分割線路的傳輸時間形成多個子信道（一個時間片）時隙
3， 統計時分多路復用（STDM）：分割線路的傳輸時間。但動不是固定給用戶分配時間片，而是需要傳送時，才給它分配時間片。
4， 波分多路復用（WOM）：光纖上使用分割的是信號光的波長
27．頻分多路復用的工作原理
28．時分多路復用的種類和各自的工作特性
29．會話層的同步方法
為了控制信息流同時能夠從軟體或操作失誤中恢復過來，會話層允許在數據中插入同步點，當出現故障時，找到故障處的前一個同步點並從該同步點進行恢復，這個過程稱為再同步。對話過程中可以插入次同步點，如果傳輸中出了故障，控制流可以退回到對話中的一個或多個次同步上進行恢復。主同步點必須被確認，次同步點不需要確認。
30．表示層的局部語法和傳送語法
局部語法：某一具體計算機所使用的語法稱為局部語法。局部語法的差異使得同一數據對象在不同的計算機中被表示成不同的比特序列。
傳送語法：符全傳送過程要求的語法。數據以傳送語法的形式在網路中傳送，發送方將符合自己局部語法的比特序列轉換成符合傳送語法的比特序列。
31．交換機的交換結構和各自的特點
交換結構有：軟體執行交換結構、矩陣交換結構、匯流排交換結構、共享存儲器交換結構。
軟體執行交換結構：藉助CPU和RAM的硬體環境，用特定的軟體來實現埠之間的幀交換。所有功能均由軟體來實現，操作靈活，但隨著端品數和增加，CPU的負擔加重。
矩陣交換：採用硬體方法進行交換。優點是利用硬體交換，結構緊湊，交換速度快，延遲時間短，缺點是隨著埠的增加，監控和管理變得困難。
匯流排交換：對匯流排的帶寬要求較高，造價高，但性能也好。
存儲交換：結構簡單、容易實現，但通過RAM操作會產生延時。
32．交換機的組成和各部分的主要作用
大多數交換器都有一塊背板，把各種板卡插在其上面，實現相應連接，交換器的主要部件包括控制、邏輯、陣列、及埠四個。
1， 控制部件：其作用是控制、管理交換器，識別連接到各埠的區域網的類型，並自動地進行交換器的測試
2， 邏輯部件：其作用是讀取輸入數據幀的目的地址，並以此目的地址與埠地址表中的內容進行比較，找出該目的地址對應的埠號，批示陣列部件按通對應的（輸出埠）矩陣開頭（來接到輸出埠）
3， 陣列部件：一旦接收到邏輯部件的指令時，啟動源埠（輸入）與目的埠（輸出）之間的交叉連接，並保持該連接直到該幀全部傳送完
4， 埠部件：可以看成一組物理介面
33．交換機的轉發率和過濾率
交換器的過濾率是在某段時間內（通常為1秒）所解釋多少幀的目的地址，這種能力稱為過濾率。
轉發率是指在某段時間內（1秒）所轉發幀的數目，稱為轉發率。
34．如何使用交換機、集線器、路由器、防火牆和常用傳輸介質組建企業網路
35．關於VLAN的定義和其主要功能（P87）
VLAN（virtual LAN）虛擬區域網：建立在物理交換機之上的，它利用軟體進行邏輯工作組的劃分和管理。
36．X．25的協議體系結構
X.25協議是CCITT關於公用數據網上以分組方式工作的DTE與DCE之間的介面標准，其功能是為公用數據網在分組交換方式下提供終端操作，它不涉及通信子網的內部結構。
層次結構：自下至上分別稱為物理級、幀級、分組級。
37．幀中繼的基本工作原理
38．ATM的協議參考模型（P141）
39．ATM交換技術的特點
特點：
（1） 採用面向連接的工作方式。
（2） 採用非同步時分多路方式
（3） 網路沒有逐段鏈路的差錯控制和流量控制。
（4） 信頭功能簡單
（5） 小的信元長度
40．ATM交換虛連接的工作過程（P132）
41．什麼是ISDN，定義了哪些設備和介面
ISDN是用來解決一些小的辦公室或撥號用戶需要比傳統電話撥號服務能提供更寬傳輸帶寬的應用，同時ISDN也可用來提供線路備份。
42．IP地址結構和子網劃分的作用
結構：每個IP地址共有32位，分為4段，以X。X。X。X表示，每個X為8位，取值為0~255。分為網路地址和主機地址兩部分，其中網路地址表示一個網路，主機地址用來表示這個網路中的一台主機。
子網劃分作用：
G. 計算機網路通訊簡答題：擴散路由演算法原理
距離矢量演算法是向相鄰節點交換自己的路由信息，每次收到新的路由信息都需要進行計算以更新路由表，收斂速度較慢；鏈路狀態演算法是向全網節點宣告自己的鏈路狀態信息，使用洪泛的方式擴散，不需要計算直接轉發信息，收斂速度較快，但需要較大的存儲空間來記錄所有節點信息。
H. 幾道「計算機網路基礎」填空題……
MAC地址與交換機埠
1.交換機自動建立和維護一個表示__MAC地址__與__交換機埠
_對應關系的交換表。
2.在路由器數據轉發的過程中，每一級路由器需要改變的地址是________________。
3.路徑選擇方法有非自適應的_________________和自適應的___________________。
4.以距離為選擇最佳路徑度量權值的路徑選擇演算法是____距離矢量演算法_____。
5.不限制路由器跳數的路由協議是___RIP______。
6.RIP路由表的確省更新時鍾為____ 30 秒_______。
7.在一根電話線上，不能同時傳輸數據和話音的廣域網連接技術是__撥號線連接____。
8.某IP數據包頭的偏移量值為12，該數據包偏移量的位元組數是______96______。
9.Ping命令測試網路連通性使用的協議是________ICMP協議_______。
10.TCP和UDP用不同的___埠___代表不同的應用進程，該值長度為___16__位（bit）。
I. 計算機網路的最短路徑演算法有哪些對應哪些協議
用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
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。