問題描述:
> 給定一個有向帶權圖 `G=(V,E)`,其中每條邊的權是一個非負實數。另外,給定 `V` 中的一個頂點,稱為源點。現在要計算從源點到所有其它各個頂點的最短路徑長度,這里的路徑長度是指路徑上經過的所有邊上的權值之和。
----
**Dijkstra算法思想:** 按各個頂點與源點之間路徑長度的遞增次序,生成源點到各個頂點的最短路徑的方法,即先求出長度最短的一條路徑,再參照它求出長度次短的一條路徑,依此類推,直到從源點到其它各個頂點的最短路徑全部求出為止。
----
**算法設計**:
- 源點u 。集合S中的頂點到源點的最短路徑的長度已經確定,集合V-S中所包含的頂點到源點的最短路徑的長度待定。
- 特殊路徑:從源點出發只經過S中的點到達V-S中的點的路徑。
- 貪心策略:選擇特殊路徑長度最短的路徑,將其相連的V-S中的頂點加入到集合S中。
**求解步驟:**
- 步驟1:設計合適的數據結構。帶權鄰接矩陣C,即如果< u, x >E,令 `C[u][x]=<u, x >` 的權值,否則,`C[u][x]=無窮`;采用數組dist來記錄從源點到其它頂點的最短路徑長度;采用數組p來記錄最短路徑;
- 步驟2:初始化。令集合S={u},對于集合V-S中的所有頂點x,設置`dist[x]=C[u][x]` ;如果頂點i與源點相鄰,設置 `p[i]=u` ,否則 `p[i]=-1`;
- 步驟3:在集合V-S中依照貪心策略來尋找使得dist[x]具有最小值的頂點t,t就是集合V-S中距離源點u最近的頂點。
- 步驟4:將頂點t加入集合S中,同時更新集合V-S;
- 步驟5:如果集合V-S為空,算法結束;否則,轉步驟6;
- 步驟6:對集合V-S中的所有與頂點t相鄰的頂點x,如果`dist[x]>dist[t]+C[t][x]`,則`dist[x]=dist[t]+C[t][x]`并設置`p[x]=t`。轉步驟3。
----
```java
public class Dijkstra {
private static final int N = Integer.MAX_VALUE;
private static final int[][] Graph = {
{0, 1, 5, N, N, N, N, N, N},
{1, 0, 3, 7, 5, N, N, N, N},
{5, 3, 0, N, 1, 7, N, N, N},
{N, 7, N, 0, 2, N, 3, N, N},
{N, 5, 1, 2, 0, 3, 6, 9, N},
{N, N, 7, N, 3, 0, N, 5, N},
{N, N, N, 3, 6, N, 0, 2, 7},
{N, N, N, N, 9, 5, 2, 0, 4},
{N, N, N, N, N, N, 7, 4, 0}};
public static void main(String[] args) {
dijkstra(0, Graph);
}
/**
* Dijkstra最短路徑。 即圖中"節點vs"到其它各個節點的最短路徑。
*
* @param vs 起始節點
* @param Graph 圖
*/
public static void dijkstra(int vs, int[][] Graph) {
int NUM = Graph[0].length;
// 前驅節點數組
int[] prenode = new int[NUM];
// 最短距離數組
int[] mindist = new int[NUM];
// 該節點是否已經找到最短路徑
boolean[] find = new boolean[NUM];
int vnear = 0;
for (int i = 0; i < mindist.length; i++) {
prenode[i] = i;
mindist[i] = Graph[vs][i];
find[i] = false;
}
find[vs] = true;
for (int v = 1; v < Graph.length; v++) {
// 每次循環求得距離vs最近的節點vnear和最短距離min
int min = N;
for (int j = 0; j < Graph.length; j++) {
if (!find[j] && mindist[j] < min) {
min = mindist[j];
vnear = j;
}
}
find[vnear] = true;
// 根據vnear修正vs到其他所有節點的前驅節點及距離
for (int k = 0; k < Graph.length; k++) {
if (!find[k] && (min + Graph[vnear][k]) < mindist[k]) {
prenode[k] = vnear;
mindist[k] = min + Graph[vnear][k];
}
}
}
for (int i = 0; i < NUM; i++) {
System.out.println("v" + vs + "...v" + prenode[i] + "->v" + i + ", s=" + mindist[i]);
}
}
}
```
----
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記