图4：Dijkstra算法

我们已经知道了深度优先搜索和广度优先搜索，适合在无权图搜索的适合使用。而在实际场景中，比如我们想获取A路口到B路口的最短路线，最短时间或者最少红绿灯的路线，就需要对一个有权图就行最短路径搜索了。Dijkstra算法就是处理有权图搜索的算法。

这种从A点到B点的最短路径算法被称为单源最短路径算法（一个顶点到一个顶点）。这样算法有很多，比如Bellford 算法、Floyd 算法等等，当然，最著名的算法还是Dijkstra算法。

分析

最短路径是一个最优解问题，对于最优解问题，我们很容易想到动态规划来解决。

对于每一个顶点v，它只能从与其连接的上个顶点集合中转移过来，我们保留起始顶点到达顶点v的最短路径长度dist。那么处理流程如下：

• 设置当前顶点V为起始顶点为S，其距离dist为0
• 遍历与当前顶点相连的所有顶点V+i，如果当前顶点的dist+ 与之连接的边的权重w < 下个顶点的dist，则更新下个顶点的dist = 当前顶点的dist + 权重w。并且将该下个顶点放入优先队列。
• 遍历完成后从优先队列取出一个顶点作为当前顶点V，重复操作，直到优先队列为空。

实现

首先我们需要保存起始顶点到每个顶点的最短距离，同时我们还需要保存在这个最短距离的情况下，这个顶点的上个顶点是是谁，这使得我们可以逆向推导出路径。

为了更好的实现路径搜索，定义接如下：

package cn.lishiyuan.algorithm.graph;  
  
import java.util.List;  
  
/**  
 * 路径搜索  
 * @param <V>  
 */  
public interface GraphPath<V> {  
    List<V> path(V from, V to);  
    int distance(V from, V to);  
}

代码实现基于[[图1：图的表示与存储]]中邻接表的实现。这里也使用到了[[堆1：堆与堆排序]]中的堆实现

package cn.lishiyuan.algorithm.graph;  
  
import cn.lishiyuan.algorithm.heap.Heap;  
import cn.lishiyuan.algorithm.queue.LeeQueue;  
import cn.lishiyuan.algorithm.queue.LinkedQueue;  
  
import java.util.*;  
  
/**  
 * 邻接表  
 */  
public class AdjacencyList<V> implements Graph<V>,TopoSort<V> {  
    // 顶点  
    private Set<V> vertices;  
    // 边  
    private Map<V,Map<V,Integer>> edges;  
  
    private GraphType type;  
  
  
    @Override  
    public List<V> path(V from, V to) {  
        // Dijkstra 最短路径算法实现  
        if (!this.vertices.contains(from) || !this.vertices.contains(to)){  
            return Collections.emptyList();  
        }  
  
        // 当前节点到起始节点的最短距离  
        Map<V,Integer> distance = new HashMap<>();  
        // 当前节点的上个节点  
        Map<V,V> before = new HashMap<>();  
        // 当前节点是否在队列中  
        List<V> inHeap = new ArrayList<>();  
  
        // 小顶堆  
        Heap<Node<V>> heap = new Heap<>(Heap.HeapType.MIN,vertices.size());  
        Node<V> fromNode = new Node<>();  
        fromNode.distance = 0;  
        fromNode.v = from;  
        inHeap.add(from);  
        heap.add(fromNode);  
  
        while (!heap.isEmpty()) {  
            Node<V> top = heap.removeTop();  
            // 已经取出  
            inHeap.remove(top.v);  
  
            // 不存在相连的边  
            Map<V, Integer> edge = edges.get(top.v);  
            if (edge == null || edge.isEmpty()){  
                continue;  
            }  
  
            for (Map.Entry<V, Integer> entry : edge.entrySet()) {  
                // 上次的最短距离  
                Integer dist = distance.get(entry.getKey());  
                // 当前距离  
                int nowDist = entry.getValue() + top.distance;  
                Node<V> node = new Node<>();  
                node.v = entry.getKey();  
                // 是否需要堆化  
                boolean needHeap = false;  
  
                if (dist == null){  
                    // 第一次  
                    node.distance = nowDist;  
                    distance.put(entry.getKey(),nowDist);  
                    before.put(entry.getKey(), top.v);  
                    needHeap = true;  
                }else if (nowDist < dist){  
                    // 已经放入过堆  
                    node.distance = nowDist;  
                    distance.put(entry.getKey(),nowDist);  
                    before.put(entry.getKey(), top.v);  
                    needHeap = true;  
                }else{  
                    // 不需要处理  
                    node.distance = dist;  
                }  
  
                if (needHeap){  
                    if (inHeap.contains(entry.getKey())) {  
                        // 更新heap  
                        heap.update(node);  
                    }else {  
                        inHeap.add(entry.getKey());  
                        heap.add(node);  
                    }  
                }  
            }  
        }  
  
        List<V> path = new ArrayList<>();  
        // 逆向推断出路径  
        if(before.containsKey(to)){  
            path.add(to);  
  
            V now = before.get(to);  
            while (now!=null){  
                path.add(now);  
                now = before.get(now);  
            }  
        }  
  
        return path;  
    }  
  
    @Override  
    public int distance(V from, V to) {  
        // Dijkstra 最短路径算法实现  
        if (!this.vertices.contains(from) || !this.vertices.contains(to)){  
            return -1;  
        }  
  
        // 当前节点到起始节点的最短距离  
        Map<V,Integer> distance = new HashMap<>();  
        // 当前节点是否在队列中  
        List<V> inHeap = new ArrayList<>();  
  
  
        Heap<Node<V>> heap = new Heap<>(Heap.HeapType.MIN,vertices.size());  
        Node<V> fromNode = new Node<>();  
        fromNode.distance = 0;  
        fromNode.v = from;  
        inHeap.add(from);  
        heap.add(fromNode);  
  
        while (!heap.isEmpty()) {  
            Node<V> top = heap.removeTop();  
            inHeap.remove(top.v);  
  
            Map<V, Integer> edge = edges.get(top.v);  
            if (edge == null || edge.isEmpty()){  
                continue;  
            }  
            for (Map.Entry<V, Integer> entry : edge.entrySet()) {  
                Integer dist = distance.get(entry.getKey());  
                int nowDist = entry.getValue() + top.distance;  
                Node<V> node = new Node<>();  
                node.v = entry.getKey();  
                boolean needHeap = false;  
                if (dist == null){  
                    node.distance = nowDist;  
                    distance.put(entry.getKey(),nowDist);  
                    needHeap = true;  
                }else if (nowDist < dist){  
                    node.distance = nowDist;  
                    distance.put(entry.getKey(),nowDist);  
                    needHeap = true;  
                }else{  
                    node.distance = dist;  
                }  
  
                if (needHeap){  
                    if (inHeap.contains(entry.getKey())) {  
                        // 更新heap  
                        heap.update(node);  
                    }else {  
                        inHeap.add(entry.getKey());  
                        heap.add(node);  
                    }  
                }  
            }  
        }  
  
        return distance.getOrDefault(to,-1);  
    }  
  
    private static class Node<V> implements Comparable<Node<V>>{  
        V v;  
        int distance;  
  
        @Override  
        public int compareTo(Node o) {  
            return distance - o.distance;  
        }  
  
        @Override  
        public boolean equals(Object obj) {  
            boolean eq= super.equals(obj);  
            if(!eq && obj instanceof Node){  
                eq = v.equals( ((Node<?>) obj).v);  
            }  
            return eq;  
        }  
    }  
  
}

需要注意的是，我为Heap堆实现添加了一个update方法，因为最短距离可能是会变化的，这就需要我们更新数据然后重新堆化：

  
public void update(T element) {  
    if (element == null) {  
        throw new IllegalArgumentException("Element cannot be null");  
    }  
    // 找到对应元素更新  
    for (int i = 0; i < size; i++) {  
        if(data[i].equals(element)){  
            data[i] = element;  
            break;        }  
    }  
  
    // 堆化  
    heapifyUp();  
}

时间复杂度

我们在需要遍历所有的边，并且就行堆化。所以总的时间复杂度是O(E×logn)其中E是边的数量。