1.         帶權(quán)圖中，邊帶有一個(gè)數(shù)字，叫做權(quán)，它可能代表距離、耗費(fèi)、時(shí)間或其他意義。

2.         帶權(quán)圖用來(lái)最常解決的問(wèn)題是最短路徑問(wèn)題（pps）。

3.         帶權(quán)圖的最小生成樹(shù)中有所有的頂點(diǎn)和連接它們的必要的邊，且這些邊的權(quán)值最小。

4.         優(yōu)先級(jí)隊(duì)列的算法可用于尋找?guī)?quán)圖的最小生成樹(shù)。

5.         解決無(wú)向帶權(quán)圖的最小生成樹(shù)的方法

1)         找到從最新的頂點(diǎn)到其他頂點(diǎn)的所有邊，這些頂點(diǎn)不能在樹(shù)的集合中，把這些邊放如優(yōu)先級(jí)隊(duì)列。

2)         找出權(quán)值最小的邊，把它和它所到達(dá)的頂點(diǎn)放入樹(shù)的集合中。

3)         重復(fù)以上步驟，直到所有頂點(diǎn)都在樹(shù)的集合中。

6.         帶權(quán)圖的最短路徑問(wèn)題可以用Dijkstra算法解決。這個(gè)算法基于圖的鄰接矩陣表示法，它不僅能找到任意兩點(diǎn)間的最短路徑，還可以找到某個(gè)指定點(diǎn)到其他所有頂點(diǎn)的最短路徑。

Dijkstra算法的思想：

以解決尋找一條從一個(gè)城市到另一個(gè)城市的費(fèi)用最低的路線為例（假設(shè)不能直接指導(dǎo)所有路線的費(fèi)用，只能直接知道到鄰接城市的費(fèi)用）

1)         每次派一個(gè)代理人到新的城市，用這個(gè)代理人提供的新信息修正和完善費(fèi)用清單，在表中之保留從源點(diǎn)到某個(gè)城市現(xiàn)在一直的最低費(fèi)用

2)         不斷向某個(gè)新城市派代理人，條件是從源點(diǎn)到那個(gè)城市的路線費(fèi)用最低。

如

7.         有時(shí)為了看出某條路線是否可能，需要?jiǎng)?chuàng)建一個(gè)連通表。在帶權(quán)圖中，用一張表給出任意兩個(gè)頂點(diǎn)間的最低耗費(fèi)，這對(duì)頂點(diǎn)可能通過(guò)幾條邊相連。這種問(wèn)題叫做每一對(duì)頂點(diǎn)之間的最短路徑問(wèn)題。Warshall算法（此算法在圖章節(jié)中詳述）能很快創(chuàng)建這樣的連通表。在帶權(quán)圖中類(lèi)似的方法叫做Floyd算法。

Floyd算法與Warshall算法的區(qū)別。在Warshall算法中當(dāng)找到一個(gè)兩段路徑時(shí)，只是簡(jiǎn)單的在表中插入1，在Floyd算法中，需要把兩端的權(quán)值相加，并插入它們的和。

8.         關(guān)于各種圖的算法的效率：

圖的表示法有兩種：鄰接矩陣和鄰接表

算法                     時(shí)間級(jí)

鄰接矩陣（所有）         O（V2）

無(wú)權(quán)鄰接表               O(V + E)

帶權(quán)鄰接表               O((E+V)logV)

Warshall和Floyd算法      O（V3）

其中V是頂點(diǎn)數(shù)量