相關文章：

1.Dijkstra算法：

http://www.wutianqi.com/?p=1890

2.Floyd算法：

http://www.wutianqi.com/?p=1903

Dijkstra算法是處理單源最短路徑的有效算法，但它局限于邊的權值非負的情況，若圖中出現權值為負的邊，Dijkstra算法就會失效，求出的最短路徑就可能是錯的。這時候，就需要使用其他的算法來求解最短路徑，Bellman-Ford算法就是其中最常用的一個。該算法由美國數學家理查德•貝爾曼（Richard Bellman, 動態規劃的提出者）和小萊斯特•福特（Lester Ford）發明。Bellman-Ford算法的流程如下：
給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，

• 數組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數組Distant[n]為, Distant[s]為0；
•  
  以下操作循環執行至多n-1次，n為頂點數：
  對于每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
  若上述操作沒有對Distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；
• 為了檢測圖中是否存在負環路，即權值之和小于0的環路。對于每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說改圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，Bellman-Ford算法尋找單源最短路徑的時間復雜度為O(V*E).

首先介紹一下松弛計算。如下圖：

松弛計算之前，點B的值是8，但是點A的值加上邊上的權重2，得到5，比點B的值（8）小，所以，點B的值減小為5。這個過程的意義是，找到了一條通向B點更短的路線，且該路線是先經過點A，然后通過權重為2的邊，到達點B。
當然，如果出現一下情況

則不會修改點B的值，因為3＋4>6。
 
Bellman－Ford算法可以大致分為三個部分
第一，初始化所有點。每一個點保存一個值，表示從原點到達這個點的距離，將原點的值設為0，其它的點的值設為無窮大（表示不可達）。
第二，進行循環，循環下標為從1到n－1（n等于圖中點的個數）。在循環內部，遍歷所有的邊，進行松弛計算。
第三，遍歷途中所有的邊（edge（u，v）），判斷是否存在這樣情況：
d（v） > d (u) + w(u,v)
則返回false，表示途中存在從源點可達的權為負的回路。
 
之所以需要第三部分的原因，是因為，如果存在從源點可達的權為負的回路。則 應為無法收斂而導致不能求出最短路徑。
考慮如下的圖：
 

經過第一次遍歷后，點B的值變為5，點C的值變為8，這時，注意權重為－10的邊，這條邊的存在，導致點A的值變為－2。（8＋ －10＝－2）
 
 

第二次遍歷后，點B的值變為3，點C變為6，點A變為－4。正是因為有一條負邊在回路中，導致每次遍歷后，各個點的值不斷變小。
 
在回過來看一下bellman－ford算法的第三部分，遍歷所有邊，檢查是否存在d（v） > d (u) + w(u,v)。因為第二部分循環的次數是定長的，所以如果存在無法收斂的情況，則肯定能夠在第三部分中檢查出來。比如
 

此時，點A的值為－2，點B的值為5，邊AB的權重為5，5 > -2 + 5. 檢查出來這條邊沒有收斂。
 
所以，Bellman－Ford算法可以解決圖中有權為負數的邊的單源最短路徑問。

個人感覺算法導論講解很不錯，把這一章貼出來和大家分享:

24.1 The Bellman-Ford algorithm

The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.

The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i ← 1 to |V[G]| - 1
3       do for each edge (u, v) ∈ E[G]
4              do RELAX(u, v, w)
5  for each edge (u, v) ∈ E[G]
6       do if d[v] > d[u] + w(u, v)
7             then return FALSE
8  return TRUE

Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the dand π values of all vertices in line 1, the algorithm makes |V| – 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.)

（單擊圖片可以放大）

Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then π[v] = u. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.

The Bellman-Ford algorithm runs in time O(V E), since the initialization in line 1 takes Θ(V) time, each of the |V| – 1 passes over the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7 takes O(E) time.

以下是Bellman-Ford代碼:

關于編程的學習，大家肯定都知道，也是大家都說來說去的，就幾句話：

1.多看書。

2.多看代碼。

3.多敲代碼。

這些我不想多說，也覺得沒有多說的必要。

經常在CSDN上看到有人問“我學習C++一段時間了，該如何進階？”，然后接著就是一大堆的人，重復這上面的三句話或者更多，我不是說這些方法是錯的，我只是認為，這樣沒有點到本質，初學者喜歡依賴于書籍，他們看書了，他們也照著書敲了代碼，但是他們就是感覺一直在基礎的層面上打轉，這是為何呢？

在C++里定義復制構造函數時，大家知道，一般對于類中含有指針的，要進行深復制，而不是淺復制。而我在這里也要講一個類似的方法，那就是關于編程的淺學習與深學習的問題。

大家在這里可以先試著想想自己平時是怎么學習編程的？遇到一個新函數、新概念，大家是看書？記住概念？看看代碼？抑或是其他？

我根據個人的理解和經驗，在沒遇到一個新知識時，我把學習這個知識點的深度分為三個層次，依次深入：

①.看了書，看了代碼。

②.在①的基礎上，照著書把代碼敲在電腦里運行了。

③.在②的基礎上，自己根據自己的理解和腦海里的記憶，不看書，把代碼敲在電腦上，并運行。

對于第①個層次，一般會發生在以下情況下：平時沒學習，考前瘋狂的看書，但是沒時間敲代碼，于是把書和代碼都用學習概念的方法—->死記，這樣，直接導致了考時忘光光，考后欲哭無淚。

對于第②個層次，大部分人應該都處于這種情況。大家平時學習時，是一種機械化的學習，也就是第②種層次所說的，照著書敲代碼，這樣雖然當時把程序運行出來了，很高興，但是，如果我接著讓你不看書，自己動手再敲一遍，有幾個人可以敲出來？抑或是，我把題目要求改一改，讓你們用這個新學到的方法做，有幾個人可以做出來？

這就是第②種層次的弊病，網上很多人都建議，自己動手把代碼敲在電腦上，但是我相信，他們的本意是讓大家不看書，把代碼敲上去，而不是只是簡單的照著書敲代碼。

對于第①種層次，根本談不上是學習；而第②種層次和第③種層次，就是我在文章標題里所說的淺學習和深學習的區別。

我說了很多，可能有些人覺得是廢話，只需要一兩句就可以說清楚的。本文的目的，只是為了分析淺層次與深層次學習的區別，進而能自己去區別學習層次，雖然一兩句話也可以說清楚，但是卻無法印刻在讀者的腦海里，更無法自己去形成這個概念，也就無法判斷自己的學習是否到位。

最后，我像把文章用幾句話總結一下：

1.學習編程，要完成三個步驟：

        ①：看書，看代碼；

        ②：對照著書敲代碼；

        ③：拋開書本，自己根據自己理解，去敲代碼，或者自己給個題目，然后用新學到的知識去解決；

2.學習編程，如果只做到上面兩個層次，不如不學，把時間留著去打會球，因為這樣根本沒學到知識，當然，不排除有些人記憶力超強。

3.以上學習方法可以運用到其他學習上去。大家自行去理解，尋找一套適合自己的學習方法。

Tanky Woo原創，歡迎轉載，轉載請注明作者信息以及本博客：http://m.shnenglu.com/tanky-woo/

雖然這個問題已經在網上被討論遍了，但是最近從新拾起算法，感覺有必要夯實一下基礎。

棋盤覆蓋問題：
首先大致描述一下題目：
在一個2^k×2^k個方格組成的棋盤中,若有一個方格與其他方格不同,則稱該方格為一特殊方格,且稱該棋盤為一個特殊棋盤.顯然特殊方格在棋盤上出現的位置有4^k種情形.因而對任何
k≥0,有4^k種不同的特殊棋盤.
下圖–圖(1)中的特殊棋盤是當k=2時16個特殊棋盤中的一個：

 

圖(1)

題目要求在棋盤覆蓋問題中,要用下圖—圖(2)所示的4種不同形態的L型骨牌覆蓋一個給定的特殊棋盤上除特殊方格以外的所有方格,且任何2個L型骨牌不得重疊覆蓋.

 

圖(2)

思路分析：
當k>0時,將2^k×2^k棋盤分割為4個2^k－1×2^k－1子棋盤,如下圖–圖(3)所示：

 

圖(3)

特殊方格必位于4個較小子棋盤之一中,其余3個子棋盤中無特殊方格.為了將這3個無特殊方格的子棋盤轉化為特殊棋盤,可以用一個L型骨牌覆蓋這3個較小棋盤的會合處。
如下圖–圖(4)所示,這3個子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格,從而原問題轉化為4個較小規模的棋盤覆蓋問題.遞歸地使用這種分割,直至棋盤簡化為1×1棋盤。

以下是代碼：

 

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
棋盤覆蓋問題
分治法
2010-12-3
*/
#include <iostream>
using namespace std;
const int N = 11;
int Board[N][N];
int tile = 0;
 
/*
tr:棋盤左上角方格的行號
tc:棋盤左上角方格的列號
dr:特殊方格所在的行號
dc:特殊方格所在的列號
size:方形棋盤的邊長
*/
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    if(size == 1)
        return;
    int t = ++tile, s = size/2;
 
    //覆蓋左上角子棋盤
    if(dr<tr+s && dc<tc+s)
        //特殊方格在此棋盤中
        ChessBoard(tr, tc, dr, dc, s);
    else   // 此棋盤無特殊方格
    {
        // 用t號L型骨型牌覆蓋右下角
        Board[tr+s-1][tc+s-1] = t;
        // 覆蓋其余方格
        ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
    }
 
    //覆蓋右上角子棋盤
    if(dr<tr+s && dc>=tc+s)
        ChessBoard(tr, tc+s, dr, dc, s);
    else
    {
        Board[tr+s-1][tc+s] = t;
        ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
    }
 
    //覆蓋左下角子棋盤
    if(dr>=tr+s && dc<tc+s)
        ChessBoard(tr+s, tc, dr, dc, s);
    else
    {
        Board[tr+s][tc+s-1] = t;
        ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
    }
 
    //覆蓋右下角子棋盤
    if(dr>=tr+s && dc>=tc+s)
        ChessBoard(tr+s, tc+s, dr, dc, s);
    else
    {
        Board[tr+s][tc+s] = t;
        ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
    }
}
 
void DisplayBoard(int size)
{
    for(int i=1; i<=size; ++i)
    {
        for(int j=1; j<=size; ++j)
            printf("%2d ", Board[i][j]);
        printf("\n");
    }
}
 
int main()
{
    ChessBoard(1, 1, 1, 2, 4);
    DisplayBoard(4);
    return 0;
}