在上一篇博文里紊浩，我記錄了最小生成樹的算法實(shí)現(xiàn)，而在這篇里疗锐，我們來講講查找最短路徑的算法坊谁，Dijkstra算法。
Dijkstra's algorithm常用于路由算法或者作為其他圖算法的一個(gè)子模塊滑臊。距離來說口芍，如果我們將圖的頂點(diǎn)理解為每個(gè)城市，而邊上的權(quán)重表示城市間開車行徑的路徑雇卷，該算法可以用來找到兩個(gè)城市之間的最短路徑鬓椭。
Dijkstra算法是通過為每個(gè)頂點(diǎn)v保留目前為止所找到的從s到v的最短路徑來工作的颠猴。初始時(shí)，原點(diǎn)s的路徑權(quán)重被賦為0（d[s] = 0)小染。若對于頂點(diǎn)s存在能直接到達(dá)的邊翘瓮，則比較路徑的長度，如果路徑更短則更新存儲(chǔ)的值裤翩，當(dāng)算法結(jié)束時(shí)资盅，d[v]中存儲(chǔ)的便是從s到v的最短路徑，或者如果路徑不存在的話則是無法訪問踊赠，用marked數(shù)組來記錄從s到點(diǎn)v是否存在路徑呵扛。下面我們來看Dijkstra算法的代碼實(shí)現(xiàn)，首先是C++版本：
#include <iostream>
#include <vector>
#include <stack>
#include "Edge.h"
#include "IndexMinHeap.h"
using namespace std;
// Dijkstra算法求最短路徑
template <typename Graph, typename Weight>
class Dijkstra {
private:
Graph &G; // 圖的引用
int s; // 起始點(diǎn)
Weight *distTo; // distTo[i]存儲(chǔ)從起始點(diǎn)s到i的最短路徑長度
bool *marked; // 標(biāo)記數(shù)組臼疫，在算法運(yùn)行過程中標(biāo)記節(jié)點(diǎn)i是否被訪問
vector<Edge<Weight> *> from; // from[i]記錄最短路徑中择份，到達(dá)i點(diǎn)的邊是哪一條
// 可以用來恢復(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());
// 對于起始點(diǎn)s進(jìn)行初始化
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, 0);
ipq.insert(s, distTo[s]);
marked[s] = true;
while( !ipq.isEmpty() ) {
int v = ipq.extractMinIndex();
// distTo[v] 就是s到v的最短距離
marked[v] = true;
// 對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)的最短路徑還沒有找到
if ( !marked[w] ) {
// 如果w點(diǎn)以前沒有訪問過
// 或者訪問過烫堤，但是通過當(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)的最短路徑長度
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)過的邊存放在vec中
void shortestPath( int w, vector< Edge<Weight> > &vec ) {
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
// 通過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;
}
}
}
};
之后是java版本的:
// Dijkstra算法求最短路徑
public class Dijkstra<Weight extends Number & Comparable> {
private WeightedGraph G; // 圖的引用
private int s; // 起始點(diǎn)
private Number[] distTo; // distTo[i]存儲(chǔ)從起始點(diǎn)s到點(diǎn)i的最短路徑長度
private boolean[] marked; // 標(biāo)記數(shù)組，在算法運(yùn)行過程中標(biāo)記節(jié)點(diǎn)是否被訪問
private Edge<Weight>[] from; // 可以用來恢復(fù)整個(gè)最短路徑
// 構(gòu)造函數(shù)富蓄，使用Dijkstra算法求最短路徑
Dijkstra(WeightedGraph graph, int s) {
// 算法初始化
this.G = graph;
assert s >= 0 && s < G.V();
this.s = s;
distTo = new Number[G.V()];
for (int i = 0; i < G.V(); i++) {
distTo[i] = 0.0;
marked[i] = false;
from[i] = null;
}
// 使用索引堆記錄當(dāng)前找到的每個(gè)到達(dá)頂點(diǎn)的最短距離 iikkkkkk
IndexMinHeap<Weight> ipq = new IndexMinHeap<Weight>(G.V());
// 對于起始點(diǎn)s進(jìn)行初始化
distTo[s] = 0.0;
from[s] = new Edge<Weight>(s, s, (Weight)(Number)(0.0));
ipq.insert(s, (Weight) distTo[s]);
marked[s] = true;
while (!ipq.isEmpty()) {
int v = ipq.extractMinIndex();
// distTo[v]就是s到v的最短距離
marked[v] = true;
// 對v的所有相鄰節(jié)點(diǎn)進(jìn)行更新
for (Object item : G.adj(v)) {
Edge<Weight> e = (Edge<Weight>) item;
int w = e.other(v);
// 如果s點(diǎn)到w點(diǎn)的最短路徑還沒有找到
if (!marked[w]) {
// 如果w點(diǎn)以前沒有訪問過
// 或者訪問過剩燥，但是通過當(dāng)前v點(diǎn)到w點(diǎn)的距離g更短，則進(jìn)行更新
if (from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue()) {
distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
from[w] = e;
if ( ipq.contain(w) ) {
ipq.change(w, (Weight) distTo[w]);
} else {
ipq.insert(w, (Weight) distTo[w]);
}
}
}
}
}
}
// 返回從s點(diǎn)到w點(diǎn)的最短路徑長度
public Number shortestPathTo(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);
return distTo[w];
}
// 判斷從s點(diǎn)到w點(diǎn)是否聯(lián)通
public boolean hasPathTo(int w) {
assert w >= 0 && w < G.V();
return marked[w];
}
// 尋找從s點(diǎn)到w點(diǎn)的最短路徑立倍，將整個(gè)路徑存放在vec中
private Vector<Edge<Weight>> shortestPath(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);
// 通過from數(shù)組逆向查找從s到w的路徑灭红，存放到棧中
Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
Edge<Weight> e = from[w];
while (e.v() != this.s) {
s.push(e);
e = from[e.v()];
}
s.push(e);
// 從棧中依次取出元素，獲得順序的從s到w的路徑
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
while (!s.isEmpty()) {
e = s.pop();
res.add(e);
}
return res;
}
// 打印出從s點(diǎn)到w點(diǎn)的路徑
public void showPath(int w){
assert w >= 0 && w < G.V();
assert hasPathTo(w);
Vector<Edge<Weight>> path = shortestPath(w);
for( int i = 0 ; i < path.size() ; i ++ ){
System.out.print( path.elementAt(i).v() + " -> ");
if( i == path.size()-1 )
System.out.println(path.elementAt(i).w());
}
}
}
