一、简介
Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra于1959年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
二、中心思想
对于每次查询，从尚未求出距离起点最短路径的点中，选择目前距离起点最小的点，将该点距离起点的距离作为距离起点的最短路径（贪心），然后以该点为桥梁，刷新其余未求出距离起点最短路径的点的距离起点的路径：
假设桥梁为B，如果A-->C的距离大于A-->B-->C的距离，则说明由A经B到达C的路径比A直接到达C的路径更短，将A-->C的最短距离更新为A-->B-->C的距离。
三、算法特征
单源最短路径：Dijkstra算法解决的是给定图中一个起点到其它所有顶点的最短路径问题，也就是单源最短路径问题。它计算的是起点到每个顶点的最短路径。
非负权重：Dijkstra算法要求图中的边权重必须为非负数，这是因为算法的核心思想是通过不断逐步扩展距离起点最近的顶点来求解最短路径。
贪心策略：Dijkstra算法采用了贪心策略，即每次选择当前距离起点最近的顶点，并对该顶点的邻居进行松弛操作。通过不断选择最短路径的顶点，逐步扩展最短路径的范围，直到找到起点到所有顶点的最短路径。
【可使用的优化方式】优先队列：Dijkstra算法使用优先队列来快速选择当前距离起点最近的顶点。通过优先队列，可以高效地选择下一个顶点，而不需要遍历所有未访问的顶点。
基于顶点的访问情况：Dijkstra算法使用一个数组来记录每个顶点的最短路径长度，通过这个数组可以确定哪些顶点已经被访问过，并且可以根据最短路径长度的大小来判断是否需要更新最短路径值。
四、基于邻接矩阵的Dijkstra算法（适用于稠密图）
/**
* 点的序号从1开始编号
*
* @param n 点的个数
* @param map 每个点之间的距离，初始值为Integer.MAX_VALUE
* @param dist 每个点到起点的最小距离，初始值为Integer.MAX_VALUE
* @param vis 已确定了最短路径的点，初始值为false
* @param start 起点
* @param end 终点
* @return 距离起点的最短路径
*/
public static int dijkstra(int n, int[][] map, int[] dist, boolean[] vis, int start, int end) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0; //起点到起点的距离为0
for (int i = 1; i <= n; i++) { //循环n次, 每次确定一个点
int t = -1; //本次将确定的最短路径的点
for (int j = 1; j <= n; j++) { //遍历找出目前距离起点最近的点
if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
vis[t] = true; //确定该点最短路
for (int j = 1; j <= n; j++) { //松弛
if (!vis[j] && map[t][j] != Integer.MAX_VALUE) {
dist[j] = Math.min(dist[j], dist[t] + map[t][j]);
}
}
}
if (dist[end] == Integer.MAX_VALUE) {
return -1;
}
else {
return dist[end];
}
}五、基于邻接表的Dijkstra算法（适用于稀疏图）
朴素方法
public static final int N = 510; //点个数
public static int[] h = new int[N]; //头节点的next指向，初始值为-1
public static int index = 0; //当前边
public static int[] dist = new int[N]; //终点到起点的距离
public static boolean[] vis = new boolean[N]; //是否已求出最短路
public static List<Edge> list = new ArrayList<>();
private static class Edge {
public int to; //边的终点
public int value; //边的权值
public int next; //边的next指向
public Edge(int to, int value, int next) {
this.to = to;
this.value = value;
this.next = next;
}
}
public static void add(int from, int to, int value) { //头插法
list.add(new Edge(to, value, h[from])); //这条边指向原来from顶点指向的边
h[from] = index++; //更新from顶点，指向这条边
}
/**
* @return start到end的最短路
* @param start 起点
* @param end 终点
* @param n 点的个数
*/
public static int dijkstra(int start, int end, int n) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0; //起点到起点的距离为0
for (int i = 1; i <= n; i ++) { //循环n次, 每次确定一个点
int t = -1;
for (int j = 1; j <= n; j ++) { //遍历找出目前距离起点最近的点
if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
vis[t] = true; //找出该点最短路
for (int j = h[t]; j != -1; j = list.get(j).next) { //从头节点遍历与该节点连通的点
Edge e = list.get(j); //得到下一条边
if (!vis[j] && dist[t] != Integer.MAX_VALUE) {
dist[e.to] = Math.min(dist[e.to], dist[t] + e.value); //松弛
}
}
}
if (dist[end] == Integer.MAX_VALUE) {
return -1;
}
else {
return dist[end];
}
}使用优先队列进行优化
public static final int N = 510; //点个数
public static int[] h = new int[N]; //头节点的next指向，初始值为-1
public static int index = 0; //当前边
public static int[] dist = new int[N]; //终点到起点的距离
public static boolean[] vis = new boolean[N]; //是否已求出最短路
public static List<Edge> list = new ArrayList<>();
private static class Edge {
public int to; //边的终点
public int value; //边的权值
public int next; //边的next指向
public Edge(int to, int value, int next) {
this.to = to;
this.value = value;
this.next = next;
}
}
private static class Point implements Comparable<Point> {
public int index; //点的序号
public Point(int index) {
this.index = index;
}
@Override
public int compareTo(Point o) { //根据点目前到起点的距离判断优先级
return Integer.compare(dist[this.index], dist[o.index]);
}
}
public static void add(int from, int to, int value) { //头插法
list.add(new Edge(to, value, h[from])); //这条边指向原来from顶点指向的边
h[from] = index++; //更新from顶点，指向这条边
}
/**
* @return start到end的最短路
* @param start 起点
* @param end 终点
*/
public static int dijkstra(int start, int end) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0; //起点到起点的距离为0
Queue<Point> queue = new PriorityQueue<>();
queue.add(new Point(start)); //起点加入优先队列
while (!queue.isEmpty()) {
int t = queue.poll().index;
if (vis[t]) { //如果此点已确定最短路径则跳过
continue;
}
vis[t] = true; //找出该点最短路
for (int j = h[t]; j != -1; j = list.get(j).next) { //从头节点遍历与该节点连通的点
Edge e = list.get(j); //得到下一条边
if (dist[e.to] > dist[t] + e.value) {
dist[e.to] = dist[t] + e.value;
queue.add(new Point(e.to)); //将更新过的目的顶点加入优先队列
}
}
}
if (dist[end] == Integer.MAX_VALUE) {
return -1;
}
else {
return dist[end];
}
}