Dijkstra算法不能解決權值為負的情況。 Bellman-Ford算法能在更一般的情況下解決最短路徑問題，即：允許權值為負。 注意，最短路徑問題實際上均不允許有負值回路（當然是從源點可達的），因為這時不存在最短路徑。總會有更短的辦法-多繞負邊回路走幾趟就是了。 首先介紹一下松弛技術（Relaxation） 對每個頂點，都設定一個屬性d[v], 用來描述從源點s到v的最短路徑上權值的上界。 一步松弛操作的結果可以看作是對限制 d[v]<=d[u] + w(u,v)的松弛,即：每次比較dv和du+w(u,v)及更新dv叫做一次 松弛操做。 通俗來說，松弛可以認為是求最短路徑時，每一次優化路徑的過程。 總結來看，引入松弛概念其實主要是為了抽象一類步驟優化操作，為了思考問題，寫僞代碼友善。比如Dijkstra寫成含有Relax的算法形式為： void Dijkstra(Graph& g, VertexNode& s) { for each vertex v in g
{ v.distance = INFINITY; v.known = false; v.path = NULL; } s.distance = 0; for (int i=0; i<g.vertexnum; i++) { vertex v = smallest unknown distance vertex; if (v==NULL) break; else v.known = true; for each w adjacent to v { if (!w.known) { Relax(w,v); } } } } 這樣，Relax部分優化操作可以獨立思考具體書寫步驟。 回到原話題為什麼Dijkstra算法不起作用，Dijkstra算法實際上相當于對每條邊執行 一次Relax操作，是以其算法複雜度為O(|E|+×)。也就是說，頂點known标記的改變，記錄了每條邊的松弛操作。而對于含有負邊的圖，known頂點會出現标記過早的情況，即一次Relax操作是不夠的。 Bellman-Ford算法的核心則是對每條邊執行多次Relax操作，進而可以取消known的标記，因為頂點的known意向可能被之後的Relax操作改變。 Relax操作有一個非常重要的性質-路徑松弛性質：如果p<v0,v1,v2,...,vk>是一個從v0到vk的最短路徑，而p的邊是按照<v0,v1>,<v1,v2>...<vk-1,vk>的順序進行松弛的，那麼d[vk]就是最短路徑長度。這個性質的保持不受其他松弛操作的影響，即使他們與p的邊上的松弛操作混在一起。 利用這個性質，我們很容易得出結論：對于一個圖所有邊均進行|V|-1次松弛操作，一定能得到最短路徑。 是以可以得到僞代碼： BellmanFord(g, s) { for (int i=0; i < g.VertexNum; i++) for each edge(u, v) in g Relax(u, v); } 算法複雜度為O(|E||V|) 另外還有一種利用類似廣度優先搜尋算法實作該算法： 這裡其實相當于對上面的算法做了一個優化：如果某次對所有邊進行Relax操作，沒有任何d值變化，則可以立即退出疊代而不需要|V|-1次疊代都做完。 void BellmanFord(Graph& g, Vertex& s)
{
queue<vertex> q;
for each vertex v in g
{
v.distance = INFINITY;
v.path = NULL;
}
s.distance = 0;
q.enqueue(s);
while (!q.Empty())
{
v = dequeue(q);
for each w adjenct to v
{
Relax(w,v)
{
if (w not in q)
q.enqueue(w);
}
}
}
}
代碼實作： #include <iostream>
#include <deque>//雙向隊列
#include <algorithm>
using namespace std;
#define MAX_VERTEX_NUM 20
#define INFINITY 2147483647
struct adjVertexNode
{
int adjVertexPosition;
int weight;
adjVertexNode * next;
};
struct VertexNode
{
char data [ 2 ];
int distance;
VertexNode * path;
adjVertexNode * list;
};
struct Graph
{
VertexNode VertexNode [ MAX_VERTEX_NUM ];
int vertexNum;
int edgeNum;
};
void CreateGraph ( Graph & g)
{
int i , j , edgeStart , edgeEnd , edgeWeight;
adjVertexNode * adjNode;
cout << "Please input vertex and edge num (vnum enum):" << endl;
cin >> g . vertexNum >> g . edgeNum;
cout << "Please input vertex information (v1)\ n note: every vertex info end with Enter" << endl;
for ( i = 0; i < g . vertexNum; i ++)
{
cin >> g . VertexNode [ i ]. data; // vertex data info.
g . VertexNode [ i ]. list = NULL;
}
cout << "input edge information(start end weight):" << endl;
for ( j = 0; j < g . edgeNum; j ++)
{
cin >> edgeStart >> edgeEnd >> edgeWeight;
adjNode = new adjVertexNode;
adjNode -> weight = edgeWeight;
adjNode -> adjVertexPosition = edgeEnd - 1; // because array begin from 0, so it is j-1
// 将鄰接點資訊插入到頂點Vi的邊表頭部,注意是頭部！！！不是尾部。
adjNode -> next = g . VertexNode [ edgeStart - 1 ]. list;
g . VertexNode [ edgeStart - 1 ]. list = adjNode;
}
}
void PrintAdjList( const Graph & g)
{
for ( int i = 0; i < g . vertexNum; i ++)
{
cout << g . VertexNode [ i ]. data << "->";
adjVertexNode * head = g . VertexNode [ i ]. list;
if ( head == NULL)
cout << "NULL";
while ( head != NULL)
{
cout << head -> adjVertexPosition + 1 << " ";
head = head -> next;
}
cout << endl;
}
}
void DeleteGraph( Graph & g)
{
for ( int i = 0; i < g . vertexNum; i ++)
{
adjVertexNode * tmp = NULL;
while( g . VertexNode [ i ]. list != NULL)
{
tmp = g . VertexNode [ i ]. list;
g . VertexNode [ i ]. list = g . VertexNode [ i ]. list -> next;
delete tmp;
tmp = NULL;
}
}
}
void BellmanFord( Graph & g , VertexNode & s)
{
deque < VertexNode *> q;
for ( int i = 0; i < g . vertexNum; i ++)
{
g . VertexNode [ i ]. distance = INFINITY;
g . VertexNode [ i ]. path = NULL;
}
s . distance = 0;
q . push_back( &s);
int counter = 0;
while( ! q . empty())
{
VertexNode * v = q . front();
q . pop_front();
if( v == NULL)
break;
adjVertexNode * head = v -> list;
while ( head != NULL)
{
VertexNode * w = & g . VertexNode [ head -> adjVertexPosition ];
if( v -> distance + head -> weight < w -> distance)
{
w -> distance = v -> distance + head -> weight;
w -> path = v;
if ( find( q . begin (), q . end (), w) == q . end())
{
q . push_back( w);
}
}
head = head -> next;
}
counter ++;
if ( counter > g . vertexNum * g . edgeNum)
{
cout << "This graph has minus value loop!" << endl;
exit( 1);
}
}
}
void PrintPath( Graph & g , VertexNode * source , VertexNode * target)
{
if ( source != target && target -> path == NULL)
{
cout << "There is no shortest path from " << source -> data << " to " << target -> data << endl;
}
else
{
if ( target -> path != NULL)
{
PrintPath( g , source , target -> path);
cout << " ";
}
cout << target -> data ;
}
}
int main( int argc , const char ** argv)
{
Graph g;
CreateGraph( g);
PrintAdjList( g);
VertexNode & start = g . VertexNode [ 0 ];
VertexNode & end = g . VertexNode [ 6 ];
BellmanFord( g , start);
cout << "print the shortest path from v1 to v7" << endl;
PrintPath( g , & start , & end);
cout << endl;
DeleteGraph( g);
return 0;
}
其中判斷含有負值回路的方法很多，這裡采用認為最多會有|V|×|E|次操作，否則存在負值回路。 使用 queue也是可以的，但要注意 relax 内部判斷要寫成：
if (find(q._Get_container().begin(), q._Get_container().end(), w) == q._Get_container().end())
略顯臃腫。 而實際上 queue也是一個container adapter，他内部封裝了deque。
運作示例：
1 含有負值權邊，但不含負值回路。
運作結果
2 含有負值回路：v6->v7->v6 (-10)
運作結果