相关文章：

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://www.cppblog.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;
}