操作步骤
(1) 初始时，S只包含起点vs；U包含除vs外的其他顶点，且U中顶点的距离为"起点vs到该顶点的距离"[例如，U中顶点v的距离为(vs,v)的长度，然后vs和v不相邻，则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
(3) 更新U中各个顶点到起点vs的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(vs,v)的距离可能大于(vs,k)+(k,v)的距离。
(4) 重复步骤(2)和(3)，直到遍历完所有顶点。
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
代码实现
package dataStructure.graph;
import java.util.ArrayList;
import java.util.List;
/**
* Dijkstra最短路径
*/
public class ShortestPathDijkstra {
private int[][] matrix;//邻接矩阵
private int N = Integer.MAX_VALUE;//表示正无穷
private String[] vertexes;//表示顶点集合
private void createGraph(int index) {
matrix = new int[index][index];
vertexes = new String[index];
int[] v0 = {0, 1, 5, N, N, N, N, N, N};
int[] v1 = {1, 0, 3, 7, 5, N, N, N, N};
int[] v2 = {5, 3, 0, N, 1, 7, N, N, N};
int[] v3 = {N, 7, N, 0, 2, N, 3, N, N};
int[] v4 = {N, 5, 1, 2, 0, 3, 6, 9, N};
int[] v5 = {N, N, 7, N, 3, 0, N, 5, N};
int[] v6 = {N, N, N, 3, 6, N, 0, 2, 7};
int[] v7 = {N, N, N, N, 9, 5, 2, 0, 4};
int[] v8 = {N, N, N, N, N, N, 7, 4, 0};
matrix[0] = v0;
matrix[1] = v1;
matrix[2] = v2;
matrix[3] = v3;
matrix[4] = v4;
matrix[5] = v5;
matrix[6] = v6;
matrix[7] = v7;
matrix[8] = v8;
vertexes[0] = "v0";
vertexes[1] = "v1";
vertexes[2] = "v2";
vertexes[3] = "v3";
vertexes[4] = "v4";
vertexes[5] = "v5";
vertexes[6] = "v6";
vertexes[7] = "v7";
vertexes[8] = "v8";
}
/**
* Dijkstra最短路径
*/
public void dijkstra(int vs){
//表示最短路径是否获取成功
boolean[] flag = new boolean[vertexes.length];
//还未求出的最短路径
int[] U = new int[vertexes.length];
//前驱顶点数组:用于打印
int[] pre = new int[vertexes.length];
//已求出的最短路径的节点
String[] S = new String[vertexes.length];
//初始化
for (int i = 0; i < vertexes.length; i ++) {
flag[i] = false;
U[i] = matrix[vs][i];
pre[i] = 0;
}
//将vs移除
S[0] = vertexes[vs];
flag[vs] = true;
U[vs] = 0;
int k = 0;
for(int i = 1; i < vertexes.length; i++){
//获取最短路径的节点:该点到vs的值最小
int min = N;
for(int j = 0; j < vertexes.length; j ++){
if(flag[j] == false && U[j] < min){
min = U[j];
k = j;
}
}
//将k放在s中
S[i] = vertexes[k];
flag[k] = true;
//更新未访问的节点:v[1]的集体加个最短路径
for (int j = 0; j < vertexes.length; j++) {
int tmp = (matrix[k][j] == N) ? N : (min + matrix[k][j]);
//未访问过且值不为0的更新
if(flag[j] == false && (tmp < U[j])){//若tmp小于U[j],只用一种可能是U[j]=0
U[j] = tmp;
pre[j] = k;//下标节点
}
}
}
//打印最短路径
System.out.println("起始顶点: " + vertexes[vs]);
for(int i = 0; i < vertexes.length; i++){
System.out.println("最短路径(" + vertexes[vs] + "," + vertexes[i] +"):" + U[i] + " ");
//输出v0->v1->v2->v4
List<String> path = new ArrayList<>();
int j = i;
while(true){
path.add(vertexes[j]);
if(j == 0){
break;
}
j = pre[j];
}
for(int x = path.size() -1; x >= 0; x--){
if(x == 0){
System.out.println(path.get(x));
}else{
System.out.print(path.get(x) + "->");
}
}
}
System.out.println("顶点放入s的顺序:");
//v0-->v1-->v2-->v4-->v3-->v5-->v6-->v7-->v8
for(int i = 0; i < vertexes.length; i++){
System.out.print(S[i]);
if(i != vertexes.length - 1){
System.out.print("-->");
}
}
}
public static void main(String[] args) {
ShortestPathDijkstra shortestPathDijkstra = new ShortestPathDijkstra();
shortestPathDijkstra.createGraph(9);
shortestPathDijkstra.dijkstra(0);
/**
起始顶点: v0
最短路径(v0,v0):0
v0
最短路径(v0,v1):1
v0->v1
最短路径(v0,v2):4
v0->v1->v2
最短路径(v0,v3):7
v0->v1->v2->v4->v3
最短路径(v0,v4):5
v0->v1->v2->v4
最短路径(v0,v5):8
v0->v1->v2->v4->v5
最短路径(v0,v6):10
v0->v1->v2->v4->v3->v6
最短路径(v0,v7):12
v0->v1->v2->v4->v3->v6->v7
最短路径(v0,v8):16
v0->v1->v2->v4->v3->v6->v7->v8
顶点放入s的顺序:
v0-->v1-->v2-->v4-->v3-->v5-->v6-->v7-->v8
*/
}
}
