最短路dijkstra模板

Posted on | In |
Words count in article: 2.4k

## 最短路dijkstra模板

  • dijkstra算法总结
  • 常用模板解决
  • 其他写法

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1874

题目

dijkstra算法总结

总结一下dijkstra算法大致的流程:

  • 一开始有一个dist[]数组(也可以是map)来保存从start(起点)到每个点的最短路径(一开始的话，如果start和某个点没有边，就为INF(或者为null)，如果有连线的话就是边的权值)；
  • 然后每次从dist数组中取出一个dist[i]最小的i(不能取已经用过的顶点(vis数组标记))，也就是start距离某个结点最近的一个；
  • 取出这个结点之后，用这个结点更新和它相连的边的dist数组；
  • 直到把所有的dist数组都更新一遍；

在这里插入图片描述

注意: dijkstra为什么不能有负权边? 因为如果有的话，我们找最小的那个结构的时候，没准它还能通过松弛变得更短，例如上面我们一开始选出0~2这条边的时候，试想如果2~1的那条边权值为-4，那一开始我们找的0~2这条边就是错的，所以不能有负权边。

常用模板解决

推荐的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.BufferedInputStream;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static boolean[] vis;
    static ArrayList<Edge> G[];


    static class Edge implements Comparable<Edge> {
        public int to;
        public int w;

        public Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return w - o.w;
        }
    }

    static int[] dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] dis = new int[n];
        for (int i = 0; i < n; i++) dis[i] = Integer.MAX_VALUE; //初始标记（不是-1(因为是求最小的)）
        dis[start] = 0;
//        G.vis[start] = true;  //第一个访问 start, 不能将start标记为true
        pq.add(new Edge(start, 0)); //将第一条边加入 pq, 自环边
        while (!pq.isEmpty()) {
            Edge curEdge = pq.poll();
            int to = curEdge.to;
            if (vis[to])
                continue;
            vis[to] = true;
            for (int i = 0; i < G[to].size(); i++) { //更新相邻的边
                int nxtNode = G[to].get(i).to;
                int nxtW = G[to].get(i).w;
                if (!vis[nxtNode] && dis[nxtNode] > dis[to] + nxtW) {
                    dis[nxtNode] = dis[to] + nxtW;
                    pq.add(new Edge(nxtNode, dis[nxtNode])); //将这个新的dis[nxtNode]加入优先队列，没准它是下一个(很小)
                }
            }
        }
        return dis;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while (cin.hasNext()) {
            n = cin.nextInt();
            m = cin.nextInt();
            G = new ArrayList[n]; // 0~n-1
            vis = new boolean[n];
            for (int i = 0; i < n; i++) {
                G[i] = new ArrayList<>();
                vis[i] = false;
            }
            for (int i = 0; i < m; i++) {
                int from = cin.nextInt();
                int to = cin.nextInt();
                int w = cin.nextInt();
                G[from].add(new Edge(to, w));
                G[to].add(new Edge(from, w));
            }
            int s = cin.nextInt();
            int e = cin.nextInt();
            int[] dis = dijkstra(s);
            System.out.println(dis[e] == Integer.MAX_VALUE ? -1 : dis[e]);
        }
    }
}

其他写法

没有使用堆优化，也就是说找出当前最小的dist所在的结构的时候，遍历了一遍当前的dist。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

    private static class Node{
        public int value;
        public ArrayList<Edge>edges;

        public Node(int value) {
            this.value = value;
            edges = new ArrayList<>();
        }
    }

    private static class Edge{
        public int weight;
        public Node from;
        public Node to;

        public Edge( Node from, Node to,int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    private static class Graph{
        public HashMap<Integer,Node>nodes;

        public Graph() {
            nodes = new HashMap<>();
        }
    }

    //没有使用堆优化的 O(n^2)
    public static HashMap<Node,Integer> dijkstra(Node head){
        HashMap<Node,Integer>dist = new HashMap<>();
        dist.put(head,0);
        for(Edge edge : head.edges){
            dist.put(edge.to,edge.weight);
        }

        HashSet<Node>set = new HashSet<>();
        for(Node minNode = getMinAndUnSelect(dist,set); minNode != null ; minNode = getMinAndUnSelect(dist,set)){
            int distance = dist.get(minNode);
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if(set.contains(toNode))continue;
                if(!dist.containsKey(toNode)){
                    dist.put(toNode,distance + edge.weight);
                }
                dist.put(toNode,Math.min(dist.get(toNode),distance + edge.weight));
            }
            set.add(minNode); //使用过这个之后就标记
        }
        return dist;
    }

    //找出dist中最小且没有选择的结点
    private static Node getMinAndUnSelect(HashMap<Node, Integer> dist, HashSet<Node> set) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Entry<Node,Integer> entry : dist.entrySet()){ // map遍历方式 https://www.cnblogs.com/fqfanqi/p/6187085.html
            Node node = entry.getKey();
            int distance = entry.getValue();
            if(!set.contains(node) && distance < minDistance){
                minDistance = distance;
                minNode = node;
            }
        }
        return minNode;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while(cin.hasNext()){
            int n = cin.nextInt();
            int m = cin.nextInt();
            Graph G = new Graph();
            for(int i = 0; i < n; i++)G.nodes.put(i,new Node(i));
            for(int i = 0; i < m; i++){
                int a = cin.nextInt();
                int b = cin.nextInt();
                int w = cin.nextInt();
                Node from = G.nodes.get(a);
                Node to = G.nodes.get(b);
                from.edges.add(new Edge(from,to,w));
                to.edges.add(new Edge(to,from,w));
            }
            int start = cin.nextInt();
            int end = cin.nextInt();
            HashMap<Node, Integer> dist = dijkstra(G.nodes.get(start));//从start开始
            Integer res = dist.get(G.nodes.get(end));
            System.out.println((res == null) ? -1 : res);
        }
    }
}

堆优化，其他写法(建图稍有不同): 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.BufferedInputStream;
import java.util.*;
import java.util.Map.Entry;

public class Main {

    static class Node{
        public int value;
        public ArrayList<Edge>edges;

        public Node(int value) {
            this.value = value;
            edges = new ArrayList<>();
        }
    }

    static class Edge{
        public int weight;
        public Node from;
        public Node to;

        public Edge( Node from, Node to,int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static class Graph{
        public HashMap<Integer,Node>nodes;

        public Graph() {
            nodes = new HashMap<>();
        }
    }

    static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    static class EdgeComparator implements Comparator<NodeRecord>{

        @Override
        public int compare(NodeRecord o1, NodeRecord o2) {
            return o1.distance - o2.distance;
        }
    }

    static HashMap<Node, Integer> dijkstra(Node head){
        HashMap<Node,Integer>dist = new HashMap<>();
        dist.put(head,0);
        for(Edge edge : head.edges){//这个不能少
            dist.put(edge.to,edge.weight);
        }
        PriorityQueue<NodeRecord>priorityQueue = new PriorityQueue<>(new EdgeComparator());
        priorityQueue.add(new NodeRecord(head,0));
        HashSet<Node>set = new HashSet<>();
        while(!priorityQueue.isEmpty()){
            NodeRecord poll = priorityQueue.poll();
            Node cur = poll.node;
            int distance = poll.distance;
            if(set.contains(cur))continue;
            set.add(cur);
            for(Edge edge : cur.edges){
                int w = edge.weight;
                Node toNode = edge.to;
                if(set.contains(toNode))continue;
                if(!dist.containsKey(toNode))dist.put(toNode,distance + w);
                dist.put(toNode,Math.min(dist.get(toNode),distance + w));
                priorityQueue.add(new NodeRecord(toNode,dist.get(toNode)));
            }
        }
        return dist;
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while(cin.hasNext()){
            int n = cin.nextInt();
            int m = cin.nextInt();
            Graph G = new Graph();
            for(int i = 0; i < n; i++)G.nodes.put(i,new Node(i));
            for(int i = 0; i < m; i++){
                int a = cin.nextInt();
                int b = cin.nextInt();
                int w = cin.nextInt();
                Node from = G.nodes.get(a);
                Node to = G.nodes.get(b);
                from.edges.add(new Edge(from,to,w));
                to.edges.add(new Edge(to,from,w)); //注意无向图
            }
            int start = cin.nextInt();
            int end = cin.nextInt();
            HashMap<Node, Integer> dist = dijkstra(G.nodes.get(start));//从start开始
            Integer res = dist.get(G.nodes.get(end));
            System.out.println((res == null) ? -1 : res);
        }
    }
}

手写堆解决写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import java.io.BufferedInputStream;
import java.util.*;

public class Main {
    static class Node{
        public int value;
        public ArrayList<Edge> edges;

        public Node(int value) {
            this.value = value;
            edges = new ArrayList<>();
        }
    }

    static class Edge{
        public int weight;
        public Node from;
        public Node to;

        public Edge( Node from, Node to,int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static class Graph{
        public HashMap<Integer,Node> nodes;

        public Graph() {
            nodes = new HashMap<>();
        }
    }

    static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    static class NodeHeap {
        private Node[] nodes;
        private HashMap<Node, Integer> indexMap;//堆的下标
        private HashMap<Node, Integer> distMap; //堆里面Node对应的distance
        private int size;

        public NodeHeap(int size) {
            nodes = new Node[size];
            indexMap = new HashMap<>();
            distMap = new HashMap<>();
            this.size = 0;
        }

        public boolean isEmpty() {//堆是否为空
            return size == 0;
        }

        public void addOrUpdateOrIgnore(Node node, int distance) {
            //如果在堆中已经有了这个结点，就要更新   -1表示的是被访问过了
            if (indexMap.containsKey(node) && indexMap.get(node) != -1) { //update contain and index != -1
                distMap.put(node, Math.min(distMap.get(node), distance));
                insertHeapify(node, indexMap.get(node));
            }

            //如果 堆中没有这个结点 就创建一个
            if (!indexMap.containsKey(node)) {//if isEntered --> ignore
                nodes[size] = node;
                indexMap.put(node, size);
                distMap.put(node, distance);
                insertHeapify(node, size++);
            }
        }

        //从堆中取一个
        public NodeRecord poll() {
            NodeRecord top = new NodeRecord(nodes[0], distMap.get(nodes[0]));//取出堆顶
            swap(0, size - 1); //和最后一个交换
            indexMap.put(nodes[size - 1], -1); //标记已经用过，相当于　Hashset作用
            distMap.remove(nodes[size - 1]);  //距离数组中李处
            nodes[size - 1] = null;  //结点数组中设置为null
            heapify(0, --size);
            return top;
        }

        private void insertHeapify(Node node, int index) { //插入并调整
            while (distMap.get(nodes[index]) < distMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int minIndex = left + 1 < size && distMap.get(nodes[left + 1]) < distMap.get(nodes[left])
                        ? left + 1 : left;
                minIndex = distMap.get(nodes[minIndex]) < distMap.get(nodes[index]) ? minIndex : index;
                if (minIndex == index) break;
                swap(minIndex, index);
                index = minIndex;
                left = index * 2 + 1;
            }
        }

        private void swap(int a, int b) {
            indexMap.put(nodes[a], b);//交换各自的下标
            indexMap.put(nodes[b], a);
            Node tmp = nodes[a];
            nodes[a] = nodes[b];
            nodes[b] = tmp;
        }
    }

    static HashMap<Node,Integer> dijkstra(Graph G,int start){
        NodeHeap heap = new NodeHeap(G.nodes.size());
        heap.addOrUpdateOrIgnore(G.nodes.get(start),0);
        HashMap<Node,Integer>dist = new HashMap<>();
        while(!heap.isEmpty()){
            NodeRecord poll = heap.poll();
            Node cur = poll.node;
            int distance = poll.distance;
            for(Edge edge : cur.edges){
                heap.addOrUpdateOrIgnore(edge.to, distance + edge.weight);
            }
            dist.put(cur,distance);
        }
        return dist;
    }


    static Graph createGraph(Scanner cin,int n,int m){
        Graph G = new Graph();
        for(int i = 0; i < n; i++)G.nodes.put(i,new Node(i));
        for(int i = 0; i < m; i++){
            int a = cin.nextInt();
            int b = cin.nextInt();
            int w = cin.nextInt();
            Node from = G.nodes.get(a);
            Node to = G.nodes.get(b);
            from.edges.add(new Edge(from,to,w));
            to.edges.add(new Edge(to,from,w));
        }
        return G;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while(cin.hasNext()){
            int n = cin.nextInt();
            int m = cin.nextInt();
            Graph G = createGraph(cin,n,m);
            int start = cin.nextInt();
            int end = cin.nextInt();
            HashMap<Node, Integer> dist = dijkstra(G,start);//从start开始
            Integer res = dist.get(G.nodes.get(end));
            System.out.println((res == null) ? -1 : res);
        }
    }
}
欢迎关注我们的公众号
0%