什么是最短路径问题？
在许多考题中，常常会有这样的问法，在图中，如何求顶点A到顶点G的最短路径？
对于最短路径问题来说，我们常用的解题算法就是迪杰斯特拉和弗罗伊德算法。当然对于无权图来说，我们通过广度优先遍历也能得出最短距离，当目标顶点最早从第几层出现，最短距离就是几。
迪杰斯特拉算法（Dijkstra）
迪杰斯特拉算法是著名的单源最短路径算法。我们可以通过迪杰斯特拉算法得到起点与其它各个顶点之间的距离表。
单源就是指起点固定。
时间复杂度（O(n²)）,此处可借助最小堆优化，不需要每次再去比较大小时间复杂度降为（O(elogn)）[图有e条边]
迪杰斯特算法步骤：
- 创建距离表 key 是对应其他顶点，Value是起点A到对应顶点的已知最短距离（默认值初始化为Max）;
- 遍历起点A，找到起点A的邻接顶点B和C。得到A到B的距离，A到C的距离，把这些信息刷新到距离表当中;
- 从距离表中找到从A出发距离最短的点，也就是顶点C;
- 遍历顶点C，找到顶点C的邻接顶点D和F（不考虑已经遍历过的点）。得到C到D的距离，从而可以得到A到D的最短距离；得到C到F的距离，从而得到A到F的最短距离，把这些信息刷新到距离表中：
- 重复上述操作，直到把A到所有点的路线遍历一遍，将最短距离刷新到表中为止
package com.zhj.interview;
import java.util.*;
public class TestDijkstra {
public static void main(String[] args) {
Graph graph = new Graph(7);
initGraph(graph);
Map<Integer, Integer> distanceMap = dijkstra(graph, 0);
System.out.println(distanceMap.get(6));
}
/*
* Dijkstra算法
*/
public static Map<Integer, Integer> dijkstra(Graph graph, int startIndex) {
// 初始化
Map<Integer, Integer> distanceMap = new HashMap<>();
Set<Integer> accessedSet = new HashSet<>();
accessedSet.add(startIndex);
int size = graph.vertices.length;
for (int i = 0; i < size; i++) {
if (i != startIndex) {
distanceMap.put(i, Integer.MAX_VALUE);
}
}
for (Edge edge : graph.adj[startIndex]) {
distanceMap.put(edge.index, edge.weight);
}
for (int i = 0; i < size; i++) {
if (i != startIndex) {
// 最短路径
int minDistanceFromStart = Integer.MAX_VALUE;
int minDistanceIndex = -1;
for (int j = 0; j < size; j++) {
if (j != startIndex && !accessedSet.contains(j) && distanceMap.get(j) < minDistanceFromStart) {
minDistanceFromStart = distanceMap.get(j);
minDistanceIndex = j;
}
}
if (minDistanceIndex == -1) {
break;
}
accessedSet.add(minDistanceIndex);
for (Edge edge : graph.adj[minDistanceIndex]) {
if (accessedSet.contains(edge.index)) {
continue;
}
int weigth = edge.weight;
int preDistance = distanceMap.get(edge.index);
if (weigth != Integer.MAX_VALUE && (minDistanceFromStart + weigth) < preDistance) {
distanceMap.put(edge.index, minDistanceFromStart + weigth);
}
}
}
}
return distanceMap;
}
/*
* 顶点
*/
private static class Vertex {
String data;
Vertex(String data) {
this.data = data;
}
}
/*
* 边
*/
private static class Edge {
int index;
int weight;
Edge(int index, int weight) {
this.index = index;
this.weight = weight;
}
}
/*
* 图
*/
private static class Graph {
private Vertex[] vertices;
private LinkedList<Edge> adj[];
Graph(int size) {
vertices = new Vertex[size];
adj = new LinkedList[size];
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
}
/*
* 初始化图
*/
private static void initGraph(Graph graph) {
graph.vertices[0] = new Vertex("A");
graph.vertices[1] = new Vertex("B");
graph.vertices[2] = new Vertex("C");
graph.vertices[3] = new Vertex("D");
graph.vertices[4] = new Vertex("E");
graph.vertices[5] = new Vertex("F");
graph.vertices[6] = new Vertex("G");
graph.adj[0].add(new Edge(1,7));
graph.adj[0].add(new Edge(2,6));
graph.adj[1].add(new Edge(0,7));
graph.adj[1].add(new Edge(3,3));
graph.adj[1].add(new Edge(5,4));
graph.adj[2].add(new Edge(0,6));
graph.adj[2].add(new Edge(3,1));
graph.adj[2].add(new Edge(4,4));
graph.adj[3].add(new Edge(1,3));
graph.adj[3].add(new Edge(2,1));
graph.adj[3].add(new Edge(4,5));
graph.adj[3].add(new Edge(5,1));
graph.adj[4].add(new Edge(2,4));
graph.adj[4].add(new Edge(3,5));
graph.adj[4].add(new Edge(6,2));
graph.adj[5].add(new Edge(1,4));
graph.adj[5].add(new Edge(3,1));
graph.adj[5].add(new Edge(6,6));
graph.adj[6].add(new Edge(4,2));
graph.adj[6].add(new Edge(5,6));
}
}
弗罗伊德算法（Floyd）
如果题目变为，图中所有顶点两两之间的最短距离呢？虽然说使用迪杰斯特拉算法也可以求得这道题的结果，但是迪杰斯特拉算法本身时间复杂度就过高，再对每个点都用一次，时间复杂度（O(n³)）。
这时候就到了弗洛伊德算法出场的时机了，弗洛伊德就是求带权图中多源点之间最短路径的算法。
弗罗伊德算法的核心是利用两点之间的中继顶点，一步一步推出所有顶点的最短距离的。
弗罗伊德算法步骤：
- 创建带权图的领接矩阵
在邻接矩阵当中，每一个数字代表着从某个顶点到另一个顶点的直接距离，这个距离是没有涉及到任何中继顶点的。
- 这时我们假定只允许以顶点A作为中继顶点，那么各顶点之间的距离会变成什么样子呢？
B和C之间的距离原本是无穷大，此时以A为中继，距离缩短为AB距离+AC距离=7+6=13，更新对应矩阵元素
- 接下来，我们以顶点A、B两点作为中继顶点，那么各顶点之间的距离会变成什么样子呢？
A和D之间的距离原本是无穷大，此时以B为中继，距离缩短为AB距离+BD距离=7+3=10,A和F之间的距离原本是无穷大，此时以B为中继，距离缩短为AB距离+BF距离=7+4=11,更新对应矩阵元素。
- 接下来，以A、B、C三点，以此类推所有点都可以是中继点（如果遇到重复的取最小值）
- 最后就得到全部点到点的最短距离
代码实现：
package com.zhj.interview;
public class TestFloyd {
public static void main(String[] args) {
int[][] matrix = {
{0,7,6,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
{7,0,Integer.MAX_VALUE,3,Integer.MAX_VALUE,4,Integer.MAX_VALUE},
{6,Integer.MAX_VALUE,0,1,4,Integer.MAX_VALUE,Integer.MAX_VALUE},
{Integer.MAX_VALUE,3,1,0,5,1,Integer.MAX_VALUE},
{Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,0,Integer.MAX_VALUE,2},
{Integer.MAX_VALUE,4,Integer.MAX_VALUE,1,Integer.MAX_VALUE,0,6},
{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,2,6,0}
};
floyd(matrix);
}
public static void floyd(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
for (int k = 0; k < matrix.length; k++) {
if (matrix[j][i] == Integer.MAX_VALUE || matrix[i][k] == Integer.MAX_VALUE) {
continue;
}
matrix[j][k] = Math.min(matrix[j][k],matrix[j][i] + matrix[i][k]);
}
}
}
System.out.println("最短路径矩阵：");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
}
