算法概述
迪杰斯特拉算法解决了如何在一个图中，计算某一个节点到图中其他所有节点的最短路径。如果将全国所有城市当做节点，连接两个城市的铁路当做线，那么迪杰斯特拉算法可以求出，厦门到全国其他城市的最省时的出行路线。
维基百科中的专业描述
算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。
算法描述
- 将图中的顶点分为两个部分，一个是已知最短路径的顶点，记为集合P，一个是暂时还未知最短路径的顶点，记为集合Q。数组ds[i]，表示源点到顶点i的最短路径,数组e[i][j]表示顶点i到j的距离
- 初始时，集合P中只有源点S，ds[0]=0，然后从集合Q中，找到离源点S最近的顶点u，并将u加入到集合P中。然后判断所有以u为起点的边，假设存在边uv，如果e[s][u] + e[u][v] < e[s][v], 则更新源点S到顶点v的最短路径
- 重复步骤2，直到集合Q为空，算法结束
算法示例
- 初始时，集合P={1},Q={2,3,4,5,6}, ds={0,-,-,-,-,-},-表示距离无穷大
- 在Q中找到离顶点1最近的点，可以看到是顶点2，于是P={1,2}, Q={3,4,5,6} ds={0,1,12,-,-,-}
- 更新所有以顶点2为起点的边(e[2][3],e[2][4])，因为e[1][2] + e[2][3] < e[1][3]，所以更新ds[3]=10, 同理e[1][2] + e[2][4] < e[1][4], 所以更新ds[4]=4
- 在Q中找到离顶点2最近的点，可以看到是顶点4，于是P={1,2,4}, Q={3,5,6},在更新所有以顶点4为起点的边
- 重复上述过程
代码实现
package com.wbl;
import java.util.Arrays;
import java.util.stream.StreamSupport;
/**
* @author wbl
* @date 2019-06-30
*/
public class Dijkstra {
public int[] dijkstra(int[][] edge){
int[] ds = new int[edge.length];
//初始化最短路径，这里假设都是计算从顶点1到其他顶点的最短路径
for (int i = 1; i < ds.length; i++){
ds[i] = Integer.MAX_VALUE;
}
//用来标志以找到最短路径的顶点，若flag[i] = 1，则表示已经找到由源点到顶点i的最短路径
int[] flag = new int[edge.length];
for (int i = 0; i < edge.length; i++){
int minIndex = 0;
int minValue = Integer.MAX_VALUE;
// 找到离已知顶点最近的顶点，minIndex表示该顶点
for (int j = 0; j < edge.length; j++){
if (flag[j] == 0 && ds[j] < minValue){
minValue = ds[j];
minIndex = j;
}
}
flag[minIndex] = 1;
for (int k = 0; k < edge.length; k++){
// 收敛源点到各个顶点的距离
if (edge[minIndex][k]>0 && ds[minIndex] + edge[minIndex][k] < ds[k]){
ds[k] = ds[minIndex] + edge[minIndex][k];
}
}
}
return ds;
}
public static void main(String[] args) {
int [][] edge = new int[][]{
{0,1,12,-1,-1,-1},
{-1,0,9,3,-1,-1},
{-1,-1,0,-1,5,-1},
{-1,-1,4,0,13,15},
{-1,-1,-1,-1,0,4},
{-1,-1,-1,-1,-1,0},
};
Dijkstra dijkstra = new Dijkstra();
System.out.println(Arrays.toString(dijkstra.dijkstra(edge)));
}
}
