dijkstra單源最短路徑算法
前提：圖中不能有負(fù)權(quán)邊
因?yàn)榇嬖谪?fù)權(quán)環(huán)的話(huà)就不存在最短路徑
復(fù)雜度 O(ElogV)
// Dijkstra算法求最短路徑
template<typename Graph, typename Weight>
class Dijkstra{
private:
Graph &G; // 圖的引用
int s; // 起始點(diǎn)
Weight *distTo; // distTo[i]存儲(chǔ)從起始點(diǎn)s到i的最短路徑長(zhǎng)度
bool *marked; // 標(biāo)記數(shù)組, 在算法運(yùn)行過(guò)程中標(biāo)記節(jié)點(diǎn)i是否被訪(fǎng)問(wèn)
vector<Edge<Weight>*> from; // from[i]記錄最短路徑中, 到達(dá)i點(diǎn)的邊是哪一條
// 可以用來(lái)恢復(fù)整個(gè)最短路徑
public:
// 構(gòu)造函數(shù), 使用Dijkstra算法求最短路徑 核心代碼
Dijkstra(Graph &graph, int s):G(graph){
// 算法初始化
assert( s >= 0 && s < G.V() );
this->s = s;
distTo = new Weight[G.V()];
marked = new bool[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
distTo[i] = Weight();
marked[i] = false;
from.push_back(NULL);
}
// 使用索引堆記錄當(dāng)前找到的到達(dá)每個(gè)頂點(diǎn)的最短距離
IndexMinHeap<Weight> ipq(G.V());
// 對(duì)于其實(shí)點(diǎn)s進(jìn)行初始化
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, Weight());
ipq.insert(s, distTo[s] );
marked[s] = true;
while( !ipq.isEmpty() ){
int v = ipq.extractMinIndex();
// distTo[v]就是s到v的最短距離
marked[v] = true;
// 對(duì)v的所有相鄰節(jié)點(diǎn)進(jìn)行更新
typename Graph::adjIterator adj(G, v);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
int w = e->other(v);
// 如果從s點(diǎn)到w點(diǎn)的最短路徑還沒(méi)有找到
if( !marked[w] ){
// 如果w點(diǎn)以前沒(méi)有訪(fǎng)問(wèn)過(guò),
// 或者訪(fǎng)問(wèn)過(guò), 但是通過(guò)當(dāng)前的v點(diǎn)到w點(diǎn)距離更短, 則進(jìn)行更新
if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
distTo[w] = distTo[v] + e->wt();
from[w] = e;
if( ipq.contain(w) )
ipq.change(w, distTo[w] );
else
ipq.insert(w, distTo[w] );
}
}
}
}
}
// 析構(gòu)函數(shù)
~Dijkstra(){
delete[] distTo;
delete[] marked;
delete from[0];
}
// 返回從s點(diǎn)到w點(diǎn)的最短路徑長(zhǎng)度
Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
return distTo[w];
}
// 判斷從s點(diǎn)到w點(diǎn)是否聯(lián)通
bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() );
return marked[w];
}
// 尋找從s到w的最短路徑, 將整個(gè)路徑經(jīng)過(guò)的邊存放在vec中
void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
// 通過(guò)from數(shù)組逆向查找到從s到w的路徑, 存放到棧中
stack<Edge<Weight>*> s;
Edge<Weight> *e = from[w];
while( e->v() != this->s ){
s.push(e);
e = from[e->v()];
}
s.push(e);
// 從棧中依次取出元素, 獲得順序的從s到w的路徑
while( !s.empty() ){
e = s.top();
vec.push_back( *e );
s.pop();
}
}
// 打印出從s點(diǎn)到w點(diǎn)的路徑
void showPath(int w){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
vector<Edge<Weight>> vec;
shortestPath(w, vec);
for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> ";
if( i == vec.size()-1 )
cout<<vec[i].w()<<endl;
}
}
};
Bellman-Ford單源最短路徑算法
前提：不能有負(fù)權(quán)環(huán)
Bellman-Ford可以判斷圖中是否有負(fù)權(quán)環(huán)
復(fù)雜度O(EV)
如果一個(gè)圖沒(méi)有負(fù)權(quán)環(huán)描睦，從一點(diǎn)到另外一點(diǎn)的最短路徑宿接，最多經(jīng)過(guò)所有的V個(gè)頂點(diǎn)宫峦，有V-1條邊
否則存在頂點(diǎn)經(jīng)過(guò)了兩次德绿，即存在負(fù)權(quán)環(huán)
// 使用BellmanFord算法求最短路徑
template <typename Graph, typename Weight>
class BellmanFord{
private:
Graph &G; // 圖的引用
int s; // 起始點(diǎn)
Weight* distTo; // distTo[i]存儲(chǔ)從起始點(diǎn)s到i的最短路徑長(zhǎng)度
vector<Edge<Weight>*> from; // from[i]記錄最短路徑中, 到達(dá)i點(diǎn)的邊是哪一條
// 可以用來(lái)恢復(fù)整個(gè)最短路徑
bool hasNegativeCycle; // 標(biāo)記圖中是否有負(fù)權(quán)環(huán)
// 判斷圖中是否有負(fù)權(quán)環(huán)
bool detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
typename Graph::adjIterator adj(G,i);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
if( from[e->v()] && distTo[e->v()] + e->wt() < distTo[e->w()] )
return true;
}
return false;
}
public:
// 構(gòu)造函數(shù), 使用BellmanFord算法求最短路徑
BellmanFord(Graph &graph, int s):G(graph){
this->s = s;
distTo = new Weight[G.V()];
// 初始化所有的節(jié)點(diǎn)s都不可達(dá), 由from數(shù)組來(lái)表示
for( int i = 0 ; i < G.V() ; i ++ )
from.push_back(NULL);
// 設(shè)置distTo[s] = 0, 并且讓from[s]不為NULL, 表示初始s節(jié)點(diǎn)可達(dá)且距離為0
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, Weight()); // 這里我們from[s]的內(nèi)容是new出來(lái)的, 注意要在析構(gòu)函數(shù)里delete掉
// Bellman-Ford的過(guò)程
// 進(jìn)行V-1次循環(huán), 每一次循環(huán)求出從起點(diǎn)到其余所有點(diǎn), 最多使用pass步可到達(dá)的最短距離
for( int pass = 1 ; pass < G.V() ; pass ++ ){
// 每次循環(huán)中對(duì)所有的邊進(jìn)行一遍松弛操作
// 遍歷所有邊的方式是先遍歷所有的頂點(diǎn), 然后遍歷和所有頂點(diǎn)相鄰的所有邊
for( int i = 0 ; i < G.V() ; i ++ ){
// 使用我們實(shí)現(xiàn)的鄰邊迭代器遍歷和所有頂點(diǎn)相鄰的所有邊
typename Graph::adjIterator adj(G,i);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
// 對(duì)于每一個(gè)邊首先判斷e->v()可達(dá)
// 之后看如果e->w()以前沒(méi)有到達(dá)過(guò)荷荤， 顯然我們可以更新distTo[e->w()]
// 或者e->w()以前雖然到達(dá)過(guò), 但是通過(guò)這個(gè)e我們可以獲得一個(gè)更短的距離, 即可以進(jìn)行一次松弛操作, 我們也可以更新distTo[e->w()]
if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
distTo[e->w()] = distTo[e->v()] + e->wt();
from[e->w()] = e;
}
}
}
hasNegativeCycle = detectNegativeCycle();
}
// 析構(gòu)函數(shù)
~BellmanFord(){
delete[] distTo;
delete from[s];
}
// 返回圖中是否有負(fù)權(quán)環(huán)
bool negativeCycle(){
return hasNegativeCycle;
}
// 返回從s點(diǎn)到w點(diǎn)的最短路徑長(zhǎng)度
Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
return distTo[w];
}
// 判斷從s點(diǎn)到w點(diǎn)是否聯(lián)通
bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() );
return from[w] != NULL;
}
// 尋找從s到w的最短路徑, 將整個(gè)路徑經(jīng)過(guò)的邊存放在vec中
void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
// 通過(guò)from數(shù)組逆向查找到從s到w的路徑, 存放到棧中
stack<Edge<Weight>*> s;
Edge<Weight> *e = from[w];
while( e->v() != this->s ){
s.push(e);
e = from[e->v()];
}
s.push(e);
// 從棧中依次取出元素, 獲得順序的從s到w的路徑
while( !s.empty() ){
e = s.top();
vec.push_back( *e );
s.pop();
}
}
// 打印出從s點(diǎn)到w點(diǎn)的路徑
void showPath(int w){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
vector<Edge<Weight>> vec;
shortestPath(w, vec);
for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> ";
if( i == vec.size()-1 )
cout<<vec[i].w()<<endl;
}
}
};
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊(duì)列優(yōu)化，減少了不必要的冗余計(jì)算移稳。
另外Floyed算法可以求出無(wú)負(fù)權(quán)環(huán)的最短路徑
復(fù)雜度O(V^3)
關(guān)于最長(zhǎng)路徑：
