Dijkstra最短路径算法及其优化
直接给出Java版本的普通实现方式：
/**
* 最普通的实现形式，时间复杂度是O(n2)，空间复杂度是O(n)
* @param weight
* @param start
* @return
*/
public static int[] getDijkstraRes(int[][] weight,int start){
boolean[] visited = new boolean[weight.length];
int[] res = new int[weight.length];
for (int i = 0;i < res.length;i++){
res[i] = weight[start][i];
}
// 查找 n - 1 次（n 为节点个数），每次确定一个节点
for (int i = 1;i < weight.length;i++){
int min = Integer.MAX_VALUE;
int closedNode = 0;
// 找出一个未标记的离出发点最近的节点
for (int j = 0;j < weight.length;j++){
if (j != start && !visited[j] && res[j] < min){
min = res[j];
closedNode = j;
}
}
// 标记该节点为已经访问过
visited[closedNode] = true;
//根据加入的节点更新res数组
for(int j = 0;j < weight.length;j++){
if (j == closedNode || weight[closedNode][j] == Integer.MAX_VALUE){
//与新添加进来的节点也是不可达的，就跳过
continue;
}
if (res[closedNode] + weight[closedNode][j] < res[j]){
//更新操作
res[j] = res[closedNode] + weight[closedNode][j];
}
}
}
return res;
}
该方法是最普通的实现方式，时间复杂度在O(n^2)，空间复杂度为O(n)，那么这个算法是否有可疑优化的地方呢？
答案是有的，主要可以优化的点在于：
// 找出一个未标记的离出发点最近的节点
for (int j = 0;j < weight.length;j++){
if (j != start && !visited[j] && res[j] < min){
min = res[j];
closedNode = j;
}
}
在这个循环中，需要找到未访问过的且与已被访问的节点相连的最短的点，需要遍历所有的边，即O(n)，这里我们使用小根堆，就可以实现插入O(logn)，读取O(1)的时间复杂度，可以使得时间复杂度降低。
/**
* 作为小根堆里面元素的载体
*/
static class Edge implements Comparable<Edge>{
int val;
int to;
@Override
public int compareTo(Edge o) {
//当本val大于传入的o的val时，返回正值，即本Edge应该往后面排
return this.val - o .val;
}
Edge(int _val,int _to){
val = _val;
to = _to;
}
}
/**
* 使用了优先队列来选出与已访问集合相连的最短的节点，
* 这样方式的时间复杂度是O((n+m)logn)，会比遍历求最短节点的方法时间复杂度低
* @param weight
* @param start
* @return
*/
public static int[] getDijkstraRes2(int[][] weight,int start){
int[] res = new int[weight.length];
boolean[] visited = new boolean[weight.length];
for (int i = 0;i < weight.length;i++){
if(i != start){
res[i] = Integer.MAX_VALUE;
}
}
Queue<Edge> queue = new PriorityQueue<>();
Edge firstEdge = new Edge(0,start);
queue.add(firstEdge);
while (!queue.isEmpty()){
//把最小的那个拿出来，此时我就不用遍历
Edge pollEdge = queue.poll();
int node = pollEdge.to;
int val = pollEdge.val;
if(visited[node]){
//已经访问过了，就不要再访问了
continue;
}
res[node] = val;
visited[node] = true;
for (int j = 0;j < weight.length;j++){
if (!visited[j]
&& weight[node][j] != Integer.MAX_VALUE //必须加上这个，否则下面相加可能会溢出导致判断错误
&& res[j] > res[node] + weight[node][j]){
res[j] = res[node] + weight[node][j];
queue.add(new Edge(res[j],j));
}
}
}
return res;
}
在上面的这个版本中，时间复杂度为O((n+m)logn)，其中m是边的条数，n是点的个数。
用法举例：
public static void main(String[] args) {
int MAX = Integer.MAX_VALUE; // 无法到达时距离设为 Integer.MAX_VALUE
int[][] weight={
{0,1,12,MAX,MAX,MAX},
{MAX,0,9,3,MAX,MAX},
{MAX,MAX,0,MAX,5,MAX},
{MAX,MAX,4,0,13,15},
{MAX,MAX,MAX,MAX,0,4},
{MAX,MAX,MAX,MAX,MAX,0}
};
int start = 0; // 选择出发点
System.out.println(Arrays.toString(getDijkstraRes(weight, start)));
System.out.println(Arrays.toString(getDijkstraRes2(weight, start)));
}