最短路徑Short Path
一扬跋、相關概念
最短路徑是針對于有權圖進行分析
1). 常見應用場景
最短路徑的應用.png
本次討論是單源最短路徑(Single Source Shortest Path)，可以一個帶權圖中一個點到圖中任意一個點的最短路徑凌节。
2).【松弛操作】
松弛操作.png
如上圖所示钦听，從節(jié)點0到節(jié)點1洒试，節(jié)點0的一個鄰邊就是節(jié)點1，但是可以經過鄰邊節(jié)點2再到節(jié)點1朴上，這種通過折中的方式到達鄰邊就是松弛操作垒棋。松弛操作是最短路徑的求解核心
二、Dijkstra單元最短路徑算法
1). 算法前提以及特點
- 所求圖中不能有負權邊
- 算法復雜度為O(Elog(V)); E為邊數痪宰，V為點數
2). 算法思想
以一個圖例說明算法的思想
Dijkstra單源最短路徑算法示例.png
如圖叼架，起始點為點0，進行初始化酵镜，遍歷點0的所有鄰邊碉碉，此時從點0到點1的距離為5 (后續(xù)的舉例都以點0為參考點)，到點2的距離為2淮韭，到點3的距離為6 (將這些值放入索引堆中),由于圖中不存在負權邊，所以點0到點2最短路徑就是2贴届，因為靠粪，如果進行松弛操作，發(fā)現到點1,點3的距離已經大于2了毫蚓，由于沒有負權邊占键，所以距離不可能大于2；此時再從索引堆中彈出最小的元潘，也就是點2畔乙，然后遍歷節(jié)點2所有沒有被標記找到最短路徑的節(jié)點，此時發(fā)現到點1的距離為3翩概，覆蓋之前的記錄牲距，到點4的距離為7，到點3的距離5钥庇，小于之前的6牍鞠，覆蓋掉；按照之前的邏輯评姨，目前鄰邊最短的就是到點1难述，距離為3，因為從點4吐句，和點3再中轉到點1就不可能小于3了胁后，將點1彈出，然后遍歷點1所有沒有被標記找到最短路徑的節(jié)點嗦枢，只有點4攀芯，此時距離點4為4，而且在堆中已經最小净宵，所以點4的最短路徑確定敲才，彈出裹纳；最后只有點3，訪問點3的所有鄰邊紧武，同樣的邏輯剃氧，發(fā)現已有的距離5最小，則點3確定阻星。
3). 代碼實現
輔助數據結構IndexMinHeap朋鞍、Edge參考文章頭鏈接
Dijkstra
import java.util.Iterator;
import java.util.Stack;
import java.util.Vector;
/**
* @author Liucheng
* @since 2019-10-20
*/
public class Dijkstra<Weight extends Number & Comparable> {
private WeightedGraph G; // 圖的引用
private int s; // 起始點
private Number[] distTo; // distTo[i]存儲從起始點s到i的最短路徑長度
private IndexMinHeap<Weight> heap; // 尋找最短權值的最小索引堆。
private boolean[] marked; // 標記數組, 在算法運行過程中標記節(jié)點i是否被訪問
private Edge<Weight>[] from; // from[i]記錄最短路徑中, 到達i點的邊是哪一條,可以用來恢復整個最短路徑
// 構造函數
public Dijkstra(WeightedGraph graph, int s) {
this.G = graph;
this.s = s;
this.distTo = new Number[graph.V()];
this.heap = new IndexMinHeap<>(graph.V());
this.marked = new boolean[graph.V()];
this.from = new Edge[graph.V()];
this.shortestRoad();
}
// 使用Dijkstra算法計算最短路徑
private void shortestRoad() {
// 對起始點s進行初始化,【s -> s】 點為對應的最短路徑
this.distTo[s] = 0.0;
this.from[s] = new Edge<>(s, s, (Weight) this.distTo[s]);
this.heap.insert(s, (Weight) this.distTo[s]);
this.marked[s] = true;
// 執(zhí)行Dihkstra算法
while (!heap.isEmpty()) {
// 取出堆中的最小值妥箕，最小值對應節(jié)點就是被找到對應最短路徑的點
int v = heap.extractMinIndex();
// 從前面的循環(huán)中,v點對應的邊已經添加到了from數組中滥酥，此處標記為true,就確定了s點到v點的最短路徑！
marked[v] = true;
// 對v的所有相鄰節(jié)點進行更新
Iterator iterator = this.G.adj(v).iterator();
while (iterator.hasNext()) {
Edge<Weight> e = (Edge<Weight>)iterator.next();
// 當前訪問點的邊的另一點
int w = e.other(v);
// 如果從s點到w點的最短路徑還沒有找到
if (!marked[w]) {
// distTo[v]就是s到v的最短距離
Number curDis = distTo[v].doubleValue() + e.wt().doubleValue();
/* 如果記錄最短距離數組中對應的值為空畦幢，表示還沒有訪問到此點坎吻；
如果存在，則判斷新的路徑是否比原來找到的更短*/
if (distTo[w] == null || curDis.doubleValue() < distTo[w].doubleValue()) {
// 更新最短的值
distTo[w] = curDis;
/* 記錄當前到達w點的上一節(jié)點e,
后續(xù)執(zhí)行可能被更短的路徑方式覆蓋宇葱，也有可能此方式就為最短路徑*/
from[w] = e;
if (heap.contain(w)) {
heap.change(w, (Weight)curDis);
} else {
// 對應distTo[w] == null的情況
heap.insert(w, (Weight)curDis);
}
}
}
}
}
}
// 返回從s點到w點的最短路徑的長度
public Number shortestPathTo(int w) {
return distTo[w];
}
// 判斷從s點到w點是否聯通
private boolean hasPathTo(int w) {
return marked[w];
}
// 尋找從s到w的最短路徑瘦真，將整個路徑經過的邊存放在vec中
private Vector<Edge<Weight>> shortestPath(int w) {
assert this.hasPathTo(w);
// 通過from數組逆向查找放在棧中
Stack<Edge<Weight>> stack = new Stack<>();
Edge<Weight> weightEdge = this.from[w];
while (weightEdge.v() != this.s) {
stack.push(weightEdge);
weightEdge = from[weightEdge.v()];
}
stack.push(weightEdge);
Vector<Edge<Weight>> vec = new Vector<>(stack.size());
while (!stack.empty()) {
vec.add(stack.pop());
}
return vec;
}
// 打印出從s點到w點的路徑
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());
}
}
public static void main(String[] args) {
String filename = Thread.currentThread().getContextClassLoader().getResource("testG1.txt").getPath();
int V = 5;
SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
// Dijkstra最短路徑算法同樣適用于有向圖
//SparseGraph<int> g = SparseGraph<int>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
System.out.println("Test Dijkstra:\n");
Dijkstra<Integer> dij = new Dijkstra<Integer>(g,0);
for( int i = 1 ; i < V ; i ++ ){
if(dij.hasPathTo(i)) {
System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
dij.showPath(i);
}
else
System.out.println("No Path to " + i );
System.out.println("----------");
}
}
}
- 測試文件testG1.txt
5 8
0 1 5
0 2 2
0 3 6
1 4 1
2 1 1
2 4 5
2 3 3
3 4 2
- 測試結果
/*
Test Dijkstra:
Shortest Path to 1 : 3.0
0 -> 2 -> 1
----------
Shortest Path to 2 : 2.0
0 -> 2
----------
Shortest Path to 3 : 5.0
0 -> 2 -> 3
----------
Shortest Path to 4 : 4.0
0 -> 2 -> 1 -> 4
----------
*/
三、負權邊 Bellman-Ford單源最短路徑算法
1). 算法思想以及注意事項
- 不能存在負權環(huán)：在一個負權環(huán)中持續(xù)計算黍瞧，就沒有最短路徑了(比如從點1到點2再到點3權值和為-1诸尽，每次轉一圈就減1)
- 雖然圖中有負權邊則無法計算出最短路徑，但是可以檢測是否有負權環(huán)印颤；
- 復雜度O(EV)
- 從一點到另外一點的最短路徑您机，最多經過所有的V個頂點，有V-1條邊年局，如果可以經過V及其以上的邊际看，那么圖中就一定存在負權環(huán)。
算法思想: 利用上述4點的特性某宪，假設最壞的情況就是到每個邊的最短路徑有(v-1)條邊 (不可能成立)仿村，可以對所有的點都進行(v-1)次松弛操作，必然可以找到從原點到該點的最短路徑兴喂！如果再對每個點進行松弛操作還發(fā)現有更短的邊蔼囊，則此圖中必有負權邊！
2). 代碼實現
import java.util.Iterator;
import java.util.Stack;
import java.util.Vector;
/**
* 使用BellmanFord算法求最短路徑
* @author Liucheng
* @since 2019-10-20
*/
public class BellmanFord<Weight extends Number & Comparable> {
private WeightedGraph G; // 圖的引用
private int s; // 起始點
private Number[] distTo; // distTo[i]存儲從起始點s到i的最短路徑長度
Edge<Weight>[] from; // from[i]記錄最短路徑中, 到達i點的邊是哪一條,可以用來恢復整個最短路徑
boolean hasNegativeCycle; // 標記圖中是否有負權環(huán)
// 構造函數
public BellmanFord(WeightedGraph graph, int s) {
// 初始化
this.G = graph;
this.s = s;
this.distTo = new Number[G.V()];
this.from = new Edge[G.V()];
this.shortestRoad();
}
// 使用BellmanFord算法求最短路徑
private void shortestRoad() {
/*設置distTo[s] = 0,并且讓from[s]不為null,
表示初始節(jié)點科大且距離為0*/
distTo[s] = 0.0;
from[s] = new Edge<>(s, s, (Weight)(Number)(0.0));
/*Bellman-Ford的過程
進行V-1次循環(huán), 每一次循環(huán)求出從起點到其余所有點
最多使用pass步可到達的最短距離*/
for (int pass = 1; pass < G.V(); pass++) {
/*每次循環(huán)中對所有的邊進行一遍松弛操作
遍歷所有邊的方式是先遍歷所有的頂點,
然后遍歷和所有頂點相鄰的所有邊*/
for (int i = 0; i < G.V(); i++) {
// 使用迭代器遍歷和所有頂點相鄰的所有邊
Iterator iterator = G.adj(i).iterator();
while (iterator.hasNext()) {
Edge<Weight> e = (Edge<Weight>)iterator.next();
/*對于每一個邊首先判斷e.v()可達
之后看如果e.w()以前沒有到達過衣迷，顯然我們可以更新distTo[e.w()]
或者e.w()以前雖然到達過, 但是通過這個e我們可以獲得一個更短的距離,
即可以進行一次松弛操作, 我們也可以更新distTo[e.w()]*/
if (from[e.v()] != null &&
(from[e.w()] == null ||
distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()
)
) {
distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
from[e.w()] = e;
}
}
}
}
this.hasNegativeCycle = detectNegativeCycle();
}
// 判斷圖中是否有負權環(huán)
private boolean detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
for( Object item : G.adj(i) ){
Edge<Weight> e = (Edge<Weight>)item;
if(from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue())
return true;
}
}
return false;
}
// 返回圖中是否有負權環(huán)
public boolean negativeCycle() { return hasNegativeCycle; }
// 返回從s點到w點的最短路徑長度
public Number shortestPathTo(int w) {
assert w >= 0 && w < G.V();
assert !hasNegativeCycle;
assert hasPathTo(w);
return distTo[w];
}
// 判斷從s點到w點是否聯通
private boolean hasPathTo(int w) {
return from[w] != null;
}
// 尋找從s到w的最短路徑, 將整個路徑經過的邊存放在vec中
private Vector<Edge<Weight>> shortestPath(int w){
assert w >= 0 && w < G.V() ;
assert !hasNegativeCycle ;
assert hasPathTo(w) ;
// 通過from數組逆向查找到從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.empty() ){
e = s.pop();
res.add(e);
}
return res;
}
// 打印出從s點到w點的路徑
public void showPath(int w){
assert(w >= 0 && w < G.V());
assert(!hasNegativeCycle);
assert(hasPathTo(w));
Vector<Edge<Weight>> res = shortestPath(w);
for( int i = 0 ; i < res.size() ; i ++ ){
System.out.print(res.elementAt(i).v() + " -> ");
if( i == res.size()-1 )
System.out.println(res.elementAt(i).w());
}
}
}
四畏鼓、總結
Bellman-Ford算法的優(yōu)化：利用隊列數據結構queue-based bellman-ford算法
單源最短路徑算法
單源最短路徑算法.png
確定起始點，到任意其他點
- 所有對最短路徑算法
- Folyed算法壶谒，處理無負權環(huán)的圖云矫，O(V^3)
任意兩點的最短路徑
- 最長路徑算法
最長路徑算法.png
