在講Bellman-Ford之前先介紹另一種存儲圖的方法：鄰接表。
鄰接表
先上數(shù)據(jù)檩帐，以下是一個包含4個頂點术幔，5條邊的圖。n = 4（頂點編號為1~4）湃密， m = 5诅挑，接下來每一行3個數(shù)xyz，表示頂點x到頂點y的邊的權(quán)值為z》涸矗現(xiàn)在用鄰接表來存儲一個讀出這個圖：
<pre>
4 5
1 4 9
2 4 6
1 2 5
4 3 8
1 3 7
</pre>
創(chuàng)建三個數(shù)組拔妥，u，v达箍，w用來記錄每條邊的信息没龙，即u[i],v[i],w[i]表示第i條邊是從第u[i]號頂點到v[i]號頂點（u[i]->v[i]），且權(quán)值為w[i]缎玫。
再創(chuàng)建兩耳數(shù)組first和next硬纤，first數(shù)組的1n號分別是用來存儲1n號頂點的第一條邊的編號，初始的時候因為沒有邊加入所以都是-1碘梢，即first[u[i]]保存頂點u[i]的第一條邊的編號咬摇，next[i]存儲編號為i的邊的“下一條邊”的編號伐蒂。
將每條邊讀入上面五個數(shù)組煞躬，uvw直接賦值即可，核心為first以及next的插入,插入算法為：
<pre>
next[i] = first[u[i]]
first[u[i]] = i
</pre>插入的步驟如下圖所示：
- 創(chuàng)建完成之后的讀取就比較容易了逸邦，因為first[u[i]]保存頂點u[i]的第一條邊的編號恩沛，next[i]存儲編號為i的邊的“下一條邊”的編號。我們只需要從first[u[i]]開始遍歷就可以了缕减。
<pre>
for i in 0...4 {
var k = first[i]
while k != -1 {
print("(u[k]) (v[k]) (w[k])")
k = next[k]
}
}
</pre>
- 完整的程序：
<pre>
//4個頂點雷客，5條邊，如下【1桥狡，4搅裙，9】表示頂點1到頂點4皱卓，權(quán)重為9的一條邊
let map = [[1,4,9],
[2,4,6],
[1,2,5],
[4,3,8],
[1,3,7]]
//u,v,w數(shù)組的大小要比圖的邊的數(shù)目大1
var u:[Int] = Array.init(repeatElement(0, count: map.count + 1))
var v:[Int] = Array.init(repeatElement(0, count: map.count + 1))
var w:[Int] = Array.init(repeatElement(0, count: map.count + 1))
//first和next數(shù)組的大小要比圖的頂點的數(shù)目大1
var first:[Int] = Array.init(repeatElement(-1, count: 5))
var next:[Int] = Array.init(repeatElement(-1, count: 5))
//創(chuàng)建鄰接表
func creatMap(map:[Array<Int>]) {
for i in map.indices {
u[i] = map[i][0]
v[i] = map[i][1]
w[i] = map[i][2]
next[i] = first[u[i]]
first[u[i]] = i
}
}
//遍歷鄰接表
func listMap() {
for i in 0...4 {
var k = first[i]
while k != -1 {
print("\(u[k]) \(v[k]) \(w[k])")
k = next[k]
}
}
}
creatMap(map: map)
listMap()
/*
1 3 7
1 2 5
1 4 9
2 4 6
4 3 8
*/
</pre>
Bellman-Ford算法
Bellman-Ford算法可以解決帶有負權(quán)邊(邊的權(quán)值為負數(shù))的圖。算法非常簡單：
<pre>
for _ in 1..<(n-1) {
for i in 1...m {
if dist[v[i]] > (dist[u[i]] + w[i]) {
dist[v[i]] = (dist[u[i]] + w[i])
}
}
</pre>
- 看過我上一篇Swift最短路徑之Dijkstra(單源最短路)算法文章的應該知道
<pre>
if dist[v[i]] > (dist[u[i]] + w[i]) {
dist[v[i]] = (dist[u[i]] + w[i])
}
</pre>
這兩句代碼的意思其實松弛源點到v[i]這條邊部逮。
接下來就是對每一條邊就是松弛一遍娜汁。松弛一遍，
<pre>
for i in 1...m {
if dist[v[i]] > (dist[u[i]] + w[i]) {
dist[v[i]] = (dist[u[i]] + w[i])
}
</pre>我們來看一下具體的過程兄朋。
首先給出如下所示的一個圖掐禁，右邊是按順序給出的邊
接下來用一個dist數(shù)組來存儲1號頂點到所有頂點的距離，然后開始進行4輪對所有的邊進行松弛
這里有個問題颅和，需要進行多少輪松弛呢傅事，答案是最多n-1輪，n是頂點的個數(shù)峡扩，注意是最多２湓健！如上圖所示教届，進行第4輪松弛后般又，結(jié)果并未更改。因此巍佑，我們可以在這個地方進行優(yōu)化布轿。添加一個變量來標記在本輪松弛中是否發(fā)生了變化，如果沒有發(fā)生變化骤公，則可以提前跳出循環(huán)坏瞄。
- 完整代碼如下
<pre>
let max:Int = 10000
//5個頂點，5條邊,頂點從1開始算脆栋，邊也從1開始算
let n = 5, m = 5
let map = [[0,0,0],
[2,3,2],
[1,2,-3],
[1,5,5],
[4,5,2],
[3,4,3]]
//u,v,w數(shù)組的大小要比圖的邊的數(shù)目大1
var u:[Int] = Array.init(repeatElement(0, count: 6))
var v:[Int] = Array.init(repeatElement(0, count: 6))
var w:[Int] = Array.init(repeatElement(0, count: 6))
func bellmanFord(map:[Array<Int>]) {
for i in 1...5 {
u[i] = map[i][0]
v[i] = map[i][1]
w[i] = map[i][2]
}
var dist:[Int] = Array.init(repeatElement(max, count: 6))
dist[1] = 0
var check:Int //檢測dist是否有更新
for _ in 1..<(n-1) {
check = 0
for i in 1...m {
if dist[v[i]] > (dist[u[i]] + w[i]) {
dist[v[i]] = (dist[u[i]] + w[i])
check = 1
}
}
if check == 0 { //如果數(shù)組dist沒有更新倦卖，提前退出循環(huán)結(jié)束算法
break
}
}
print(dist)
}
bellmanFord(map: map) //0, -3, -1, 2, 4
</pre>
Bellman-Ford的隊列優(yōu)化算法
在上面介紹的Bellman-Ford算法中，在每實施一次松弛操作之后椿争，就會有一些頂點已經(jīng)求得其最短路徑怕膛，此后，這些頂點的最短路徑的值就會一直保持不變秦踪，不再受到后續(xù)松弛操作的影響褐捻，但是每次還要判斷是否需要松弛，這里浪費了時間椅邓。因此柠逞，我們可以考慮每次僅針對最短路徑值發(fā)生了變化的頂點的所有出邊執(zhí)行松弛操作。這就是Bellman-Ford的隊列優(yōu)化算法景馁。
那么板壮，如何知道當前哪些點的最短路程發(fā)生了變化呢？
用一個隊列來維護這些點合住，每次選取隊首頂點u绰精，對頂點u的所有出邊進行松弛操作撒璧。假如有一條u->v的邊，如果松弛成功(dist[v] > dist[v] + e[u][v]),則將頂點v放入隊尾笨使，需要注意的是沪悲，同一個頂點不能同時在隊列中出現(xiàn)多次，但是允許一個頂點在出隊后再入隊阱表。在將頂點u的所有的出邊松弛完畢后殿如，就將頂點u出隊。接下來不斷從隊列中取出新的隊首頂點進行如上操作最爬，直至隊列為空涉馁。這就是Bellman-Ford的隊列優(yōu)化算法。下面舉一個例子爱致。
- 新建一個圖
<pre>
//5個頂點烤送，7條邊
[1,2,2],
[1,5,10],
[2,3,3],
[2,5,7],
[3,4,4],
[4,5,5],
[5,3,6]]
</pre> - 初始化dist數(shù)組和隊列。
- 選取隊首頂點1糠悯，對頂點1所有的出邊就行松弛帮坚。頂點2，和5松弛成功互艾，分別將2和5入隊试和。
- 頂點1出隊，然后選取隊首頂點2進行如上處理纫普。注意2->5這條邊松弛成功阅悍，但因為5號頂點已經(jīng)在隊列中，所以不進行入隊操作昨稼。
- 在對2號頂點處理完畢后节视，將2號頂點出隊，再選取隊首5號頂點進行以上處理假栓，知道隊列為空寻行，具體步驟就省略了，最后處理的結(jié)果如下：
完整代碼如下：
<pre>
let max:Int = 10000
//5個頂點匾荆，7條邊,頂點從1開始算拌蜘，邊也從1開始算
let map = [[0,0,0],
[1,2,2],
[1,5,10],
[2,3,3],
[2,5,7],
[3,4,4],
[4,5,5],
[5,3,6]]
//u,v,w數(shù)組的大小要比圖的邊的數(shù)目大1
var u:[Int] = Array.init(repeatElement(0, count: 8))
var v:[Int] = Array.init(repeatElement(0, count: 8))
var w:[Int] = Array.init(repeatElement(0, count: 8))
//first和next數(shù)組的大小要比圖的頂點的數(shù)目大1
var first:[Int] = Array.init(repeatElement(-1, count: 9))
var next:[Int] = Array.init(repeatElement(-1, count: 9))
//創(chuàng)建鄰接表
func creatMap(map:[Array<Int>]) {
for i in 1...7 {
u[i] = map[i][0]
v[i] = map[i][1]
w[i] = map[i][2]
next[i] = first[u[i]]
first[u[i]] = i
}
}
func bellman_ford(map:[Array<Int>]) {
creatMap(map: map)
var dist:[Int] = Array.init(repeatElement(max, count: 6))
dist[1] = 0
var book:[Int] = Array.init(repeatElement(0, count: 8))
book[1] = 1
var queue:[Int] = Array.init(repeatElement(0, count: 100))
var head = 1,tail = 1
queue[tail] = 1
tail+=1
var k = 0
while head < tail {
k = first[queue[head]]
while k != -1 {
if dist[v[k]] > (dist[u[k]] + w[k]) {
dist[v[k]] = dist[u[k]] + w[k]
if book[v[k]] == 0 {
queue[tail] = v[k]
tail+=1
}
}
k = next[k]
}
book[queue[head]] = 0
head+=1
}
print(dist)
}
bellman_ford(map: map) //0, 2, 5, 9, 9
</pre>
