最短路徑問題
本文将解析如何使用 Dijkstra 算法求解最短路徑問題
如下圖:
就像上圖, 每一個點可以了解成一個岔路口, 線段就是路徑, 線段上的值為長度, 如何找到從 v0到各個岔路口的最小值, 也就是最短路徑問題
- **如何使用代碼表示出上圖呢? **
最短路徑問題 和 深度廣度搜尋一樣, 都是建立在圖這個資料結構上的, 是以我們可以選用鄰接表 或者是臨接矩陣 來表示上圖 , 封裝類如下:
public class Graph01 {
// 使用鄰接表的方式表示圖
private LinkedList<Edge> [] graph ;
// 圖中一共多少個點
private int size;
public Graph01(int size) {
this.size = size;
this.graph = new LinkedList[this.size];
for (int i = 0; i < size; i++) {
graph[i]=new LinkedList<>();
}
}
// 添加點的方法
public void addEdge(int s, int e, int w) {
this.graph[s].add(new Edge(s, e, w));
} 它大概長這個樣子:
- 如何表示兩點之間的邊?
一條邊有三個描述屬性, 兩邊的頂點 + 權重
// 邊的封裝類
private class Edge {
// 開始點的值
private int start;
// 結束點的值
private int end;
// 權重
private int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
} - 如何表示頂點
使用兩個屬性描述頂點, 分别是 dist 和 id , 比如我們描述 v3 , 那麼它的id = 3 , dist是到起點v0的距離, 故 dist =13
// 圖中各個點的封裝類
private class Vertex implements Comparable<Vertex> {
// 使用者指定的起點到目前點的距離
private int dist;
// 頂點的id (v1 v2 中的 1 和 2)
private int id;
public Vertex(int dist, int startId) {
this.dist = dist;
this.id = startId;
}
@Override
public int compareTo(Vertex o) {
if (o.dist > this.dist) return -1;
else return 1;
}
} - 尋找最短路徑的思路
還是看這個圖: 比如我們尋找的最短路徑就是 v0 到 其它所有的頂點的最短路徑 , 按照廣度優先順序周遊這個圖
尋找 v0 的臨接點 , 于是我們能發現 v1 v2 v4 v6 這四個點都是v0的臨界點, 然後我們分别給 v1 v2 v4 v6 這四個點做出如下的标記
v1.dist = 13 // dist表示的是 目前點到起點的距離
v2.dist = 8
v4.dist = 30
v6.dist = 32 但是我們發現, 直接相連 , 并不一定是最短的 , 就像下面這樣 , 雖然都能到v4 , 但是很顯然, 如果按照
v0 -> v2 -> v3 -> v4
會更近 , 這就意味着我們需要不斷的更新每一個節點到起點的dist值
v0.dist + v4.dist = 30
v0.dist + v2.dist + v3.dist = 19 那麼, 是否存在一個點到起點v0的dist是 百分百确定并且不會更改呢??? 沒錯,就是 它所有臨界點中, dist最小的那個點
于是, 我們的編碼流程就是下面這樣
- 找到起點
- 将起點添加進隊列(因為我們是廣度優先周遊)
- 循環周遊隊列中的值
- 如果目前點 == 結束點 , 就 break
- 從隊列中取出dist 最小的點 記作 目前點
- 找到目前點的所有直接 臨接點
- 挨個周遊根節點的臨界點
- 如何未被通路過, 并且 目前點.dist + 目前路徑的長度 < 目前點的下一個點的dist (說明找到了比原來标記的最短路徑 , 更短的路徑) , 然後 用前者更新後者的值
- 将目前點加入到可以還原路徑長度的輔助數組中
- 如果目前點的下一個點未被通路過, 标記它被通路了, 然後加入隊列中
預設所有的點的 dist = Integer.MAXVALUE
如果看這圖, 用筆跟着上面的邏輯畫一下的話, 就能發現, 确實能找到 v0到其他各個點的最短路徑, 唯一不好了解的部分就是我們用黑色加粗的地方,
我們舉例子解釋一下 , 還是上圖:
**比如, 就從開頭說 : **
通過上面的步驟4 , 我們可以周遊到v0的直接臨接點是 v4 , 這是第一次通路, 于是我們可以繼續處理, 然後我們按照 步驟4.1 進行判斷
v0.dist + 30 < v4.dist
條件滿足了(預設所有的點的 dist = Integer.MAXVALUE), 于是我們就更新
v4.dist = v0.dist + 30 < v4.dist =30
經過了幾輪循環後, 假設目前已經是v3了, 這是我們繼續來到步驟4.1中進行判斷,
v3.dist + 6 < v4.dist
我們發現也是滿足的, 因為一開始算出了 v4.dist= 30 , 于是進一步更新這個值, 使
v4.dist = v3.dist + 6
, 這樣疊代下面 , 我們就能擷取到起點 到所有點的最短路徑
public void dijkstra(int start, int end) {
// 标記是否曾通路過
boolean[] visited = new boolean[this.size];
// 還路徑
int [] resultArray = new int[this.size];
// 存放圖中的所有的頂點
Vertex[] vertices = new Vertex[this.size];
for (int i = 0; i < vertices.length; i++) {
vertices[i]=new Vertex(Integer.MAX_VALUE,i);
}
// 擷取頂點, 并賦初值為0
Vertex startVertex = vertices[0];
startVertex.dist = 0;
visited[start] = true;
// 建立隊列,并将頭結點入隊
Queue<Vertex> queue = new PriorityQueue<>();
queue.add(startVertex);
while (!queue.isEmpty()) {
// 取出目前距離開始點 dist 最近的點
Vertex minVertex = queue.poll();
// 如果已經找到了頂點就退出去
if (minVertex.id==end) break;
// 周遊目前點的所有臨接點
for (int i = 0; i < graph[minVertex.id].size(); i++) {
// 依次擷取出他們的邊
Edge edge = graph[minVertex.id].get(i);
// 根據邊的資訊, 取出它的取出它的臨界點
Vertex nextVertex = vertices[edge.end];
// 如果目前點 + 目前邊的長度 < 目前點到它臨界點nextVertex的長度 就說明找到了這個直連點更新的點路徑, 于是更新原來的直聯點的資料
if (minVertex.dist + edge.weight < nextVertex.dist) {
// 更新原來的不準确的路徑值
nextVertex.dist = minVertex.dist + edge.weight;
/**
* 數值 0 0 0 2 0 0 0
* 下标 0 1 2 3 4 5 6
*
* 下标為3位置的值為2 , 表示在圖中 vertex3的前面的vertex2
*/
resultArray[nextVertex.id]=minVertex.id;
if (!visited[nextVertex.id]){
queue.add(nextVertex);
visited[nextVertex.id]=true;
}
}
}
}
System.out.print(start);
print( start,end ,resultArray);
}
/**
* 例如:
* 數值: 0 0 0 2 3 1 1
* 下标: 0 1 2 3 4 5 6
* 我們得到 從 0 - 6 的路徑該怎麼走呢? 按照如下的順序将方法壓入棧, 彈棧時即可擷取到路徑
*
* | 0 0 |
* | 0 1 |
* | 0 6 | 方法棧
* ----------
*/
private void print(int start, int end, int[] resultArray) {
if (start==end) return;
print(start,resultArray[end],resultArray);
System.out.print("->"+end);
}