最短路径:Dijstra(迪杰斯特拉)算法

一、背景

全文根据《算法-第四版》,Dijkstra(迪杰斯特拉)算法,一种单源最短路径算法。我们把问题抽象为2步:1.数据结构抽象   2.实现。 分别对应第二章、第三章。

二、算法分析

2.1 数据结构

  顶点+边->图。注意:Dijkstra算法的限定:

  • 1.边有权重,且非负
  • 2.边有向

2.1.1 加权有向边

DirectedEdge,API抽象如下:

方法 描述
DirectedEdge(int v, int w, double weight)  构造边
double weight()  边的权重
int from()  边的起点
int to()  边的终点

 

 

 

 

 

 

 

2.1.2 加权有向图

EdgeWeightedDigraph,API抽象如下:

方法 描述
EdgeWeightedDigraph(In in)  从输入流中构造图
int V()  顶点总数
int E()  边总数
void addEdge(DirectedEdge e)  将边e添加到图中
Iterable<DirectedEdge> adj(int v)  从顶点v指出的边(邻接表,一个哈希链表,key=顶点,value=顶点指出的边链表)
Iterable<DirectedEdge> edges()  图中全部边

 

 

 

 

 

 

 

 

 

 2.1.3 最短路径

DijkstraSP, API抽象如下:

方法 描述
DijkstraSP(EdgeWeightedDigraph G, int s)  构造最短路径树
double distTo(int v)  顶点s->v的距离,初始化无穷大
boolean hasPathTo(int v)  是否存在顶点s->v的路径
Iterable<DirectedEdge> pathTo(int v)  s->v的路径,不存在为null

 

 

 

 

 

 

 

元素:

最短路径树中的边(DirectedEdge[] edgeTo):

  edgeTo[v]代表树中连接v和父节点的边(最短路径最后一条边数组),每个顶点都有一条这样的边,就组成了最短路径树。

原点到达顶点的距离:由顶点索引的数组 double[] distTo

  distTo[v] 代表原点到达顶点v的最短距离。

索引最小优先级队列: IndexMinPQ<Double> pq:

     int[] pq:索引二叉堆(元素=顶点v,对应keys[v]):数组从pq[0]代表原点其它顶点从pq[1]开始插入

     Key[] keys:元素有序数组(按照pq值作为下标赋值)存储到顶点的最短距离

 

2.2 算法核心

计算最短路径,三步骤:

  • 1.每次选取最小节顶点:如果选择?使用最小堆排序,每次取堆顶元素即可。
  • 2.遍历从顶点的发出的全部边
  • 3.放松操作

三、具体实现

3.1 构造

3.1.1 元素迭代器

因为有遍历需要,这里定义Bag<Item>类实现了Iterable<Item>迭代器接口,Item是元素。就是个简单的某个元素的迭代器基本实现。
  1 package study.algorithm.base;
  2 
  3 import java.util.Iterator;
  4 import java.util.NoSuchElementException;
  5 
  6 /**
  7  *  The {@code Bag} class represents a bag (or multiset) of 
  8  *  generic items. It supports insertion and iterating over the 
  9  *  items in arbitrary order.
 10  *  <p>
 11  *  This implementation uses a singly linked list with a static nested class Node.
 12  *  See {@link LinkedBag} for the version from the
 13  *  textbook that uses a non-static nested class.
 14  *  See {@link ResizingArrayBag} for a version that uses a resizing array.
 15  *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em> operations
 16  *  take constant time. Iteration takes time proportional to the number of items.
 17  *  <p>
 18  *  For additional documentation, see <a href="//algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
 19  *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 20  *
 21  *  @author Robert Sedgewick
 22  *  @author Kevin Wayne
 23  *
 24  *  @param <Item> the generic type of an item in this bag
 25  */
 26 public class Bag<Item> implements Iterable<Item> {
 27     /**
 28      * 首节点
 29      */
 30     private Node<Item> first;
 31     /**
 32      * 元素个数
 33      */
 34     private int n;
 35 
 36     /**
 37      * 链接表
 38      * @param <Item>
 39      */
 40     private static class Node<Item> {
 41         private Item item;
 42         private Node<Item> next;
 43     }
 44 
 45     /**
 46      * 初始化一个空包
 47      */
 48     public Bag() {
 49         first = null;
 50         n = 0;
 51     }
 52 
 53     /**
 54      * Returns true if this bag is empty.
 55      *
 56      * @return {@code true} if this bag is empty;
 57      *         {@code false} otherwise
 58      */
 59     public boolean isEmpty() {
 60         return first == null;
 61     }
 62 
 63     /**
 64      * Returns the number of items in this bag.
 65      *
 66      * @return the number of items in this bag
 67      */
 68     public int size() {
 69         return n;
 70     }
 71 
 72     /**
 73      * Adds the item to this bag.
 74      *
 75      * @param  item the item to add to this bag
 76      */
 77     public void add(Item item) {
 78         // 保留老的首节点
 79         Node<Item> oldfirst = first;
 80         // 构造一个新首节点
 81         first = new Node<Item>();
 82         // item为新首节点item
 83         first.item = item;
 84         // 新节点的next节点指向老的首节点
 85         first.next = oldfirst;
 86         n++;
 87     }
 88 
 89 
 90     /**
 91      * Returns an iterator that iterates over the items in this bag in arbitrary order.
 92      *
 93      * @return an iterator that iterates over the items in this bag in arbitrary order
 94      */
 95     @Override
 96     public Iterator<Item> iterator()  {
 97         return new LinkedIterator(first);  
 98     }
 99 
100     /**
101      * 链接迭代器,不支持移除
102      */
103     private class LinkedIterator implements Iterator<Item> {
104         private Node<Item> current;
105 
106         public LinkedIterator(Node<Item> first) {
107             current = first;
108         }
109 
110         @Override
111         public boolean hasNext()  { return current != null;                     }
112         @Override
113         public void remove()      { throw new UnsupportedOperationException();  }
114 
115         @Override
116         public Item next() {
117             if (!hasNext()) {
118                 throw new NoSuchElementException();
119             }
120             Item item = current.item;
121             // 下一节点
122             current = current.next; 
123             return item;
124         }
125     }
126 
127     /**
128      * Unit tests the {@code Bag} data type.
129      *
130      * @param args the command-line arguments
131      */
132     public static void main(String[] args) {
133         Bag<String> bag = new Bag<String>();
134         while (!StdIn.isEmpty()) {
135             String item = StdIn.readString();
136             bag.add(item);
137         }
138 
139         StdOut.println("size of bag = " + bag.size());
140         for (String s : bag) {
141             StdOut.println(s);
142         }
143     }
144 
145 }

 

3.1.2 具体构造

1. 从输入流中初始化图,输入流格式(括号内为注释,实际文件中不存在):

8(顶点数)
15(边数)
4 5 0.35(边4->5 权重=0.35)
5 4 0.35 
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

如下图中public EdgeWeightedDigraph(In in)构造方法,核心:

往邻接表(顶点作为数组下标)中添加带权重边。

  1 package study.algorithm.graph;
  2 
  3 import study.algorithm.base.*;
  4 
  5 import java.util.NoSuchElementException;
  6 
  7 /***
  8  * @Description 边权重有向图
  9  * @author denny.zhang
 10  * @date 2020/4/24 9:58 上午
 11  */
 12 public class EdgeWeightedDigraph {
 13     private static final String NEWLINE = System.getProperty("line.separator");
 14 
 15     /**
 16      * 顶点总数
 17      */
 18     private final int V;
 19     /**
 20      * 边总数
 21      */
 22     private int E;
 23     /**
 24      * 邻接表(每个元素Bag代表 由某个顶点为起点的边数组,按顶点顺序排列),adjacency list
 25      */
 26     private Bag<DirectedEdge>[] adj;
 27 
 28     /**  
 29      * 从输入流中初始化图,输入流格式:
 30      * 8(顶点数)
 31      * 15(边总数)
 32      * 4 5 0.35(每一条边 4->5 权重0.35)
 33      * 5 4 0.35
 34      * 4 7 0.37
 35      * ...
 36      *
 37      * @param  in the input stream
 38      * @throws IllegalArgumentException if {@code in} is {@code null}
 39      * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range
 40      * @throws IllegalArgumentException if the number of vertices or edges is negative
 41      */
 42     public EdgeWeightedDigraph(In in) {
 43         if (in == null) {
 44             throw new IllegalArgumentException("argument is null");
 45         }
 46         try {
 47             // 1.读取顶点数
 48             this.V = in.readInt(); 52             // 初始化邻接表
 53             adj = (Bag<DirectedEdge>[]) new Bag[V];
 54             for (int v = 0; v < V; v++) {
 55                 adj[v] = new Bag<DirectedEdge>();
 56             }
 57             // 2.读取边数
 58             int E = in.readInt();
 59             62             for (int i = 0; i < E; i++) {
 63                 int v = in.readInt();
 64                 int w = in.readInt();
 67                 // 3.读取边的权重
 68                 double weight = in.readDouble();
 69                 // 添加权重边
 70                 addEdge(new DirectedEdge(v, w, weight));
 71             }
 72         }   
 73         catch (NoSuchElementException e) {
 74             throw new IllegalArgumentException("invalid input format in EdgeWeightedDigraph constructor", e);
 75         }
 76     }
 77 
 78     /**
 79      * 顶点数
 80      *
 81      * @return the number of vertices in this edge-weighted digraph
 82      */
 83     public int V() {
 84         return V;
 85     }
 86 
 87     /**
 88      * 边数
 89      *
 90      * @return the number of edges in this edge-weighted digraph
 91      */
 92     public int E() {
 93         return E;
 94     }
 95 
106     /**
107      * 往图中添加边
108      *
109      * @param  e the edge
110      * @throws IllegalArgumentException unless endpoints of edge are between {@code 0}
111      *         and {@code V-1}
112      */
113     public void addEdge(DirectedEdge e) {
114         // 边的起点
115         int v = e.from();
116         // 边的终点
117         int w = e.to();120         // 起点v的邻接表,加入一条边
121         adj[v].add(e);
122         // 边总数+1
123         E++;
124     }
125 
126 
127     /**
128      * 返回从顶点V 指出的全部可迭代边(邻接表)
129      *
130      * @param  v the vertex
131      * @return the directed edges incident from vertex {@code v} as an Iterable
132      * @throws IllegalArgumentException unless {@code 0 <= v < V}
133      */
134     public Iterable<DirectedEdge> adj(int v) {
135         validateVertex(v);
136         return adj[v];
137     }
138 
139     /**
140      * 返回全部有向边
141      *
142      * @return all edges in this edge-weighted digraph, as an iterable
143      */
144     public Iterable<DirectedEdge> edges() {
145         Bag<DirectedEdge> list = new Bag<DirectedEdge>();
146         // 遍历全部顶点
147         for (int v = 0; v < V; v++) {
148             // 每个顶点的邻接表(指出边)
149             for (DirectedEdge e : adj(v)) {
150                 // 指出边入list
151                 list.add(e);
152             }
153         }
154         return list;
155     } 
156 
157     /**
158      * Returns a string representation of this edge-weighted digraph.
159      *
160      * @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>,
161      *         followed by the <em>V</em> adjacency lists of edges
162      */
163     @Override
164     public String toString() {
165         StringBuilder s = new StringBuilder();
166         s.append(V + " " + E + NEWLINE);
167         for (int v = 0; v < V; v++) {
168             s.append(v + ": ");
169             for (DirectedEdge e : adj[v]) {
170                 s.append(e + "  ");
171             }
172             s.append(NEWLINE);
173         }
174         return s.toString();
175     }
176 
177     /**
178      * Unit tests the {@code EdgeWeightedDigraph} data type.
179      *
180      * @param args the command-line arguments
181      */
182     public static void main(String[] args) {
183         In in = new In(args[0]);
184         EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
185         StdOut.println(G);
186     }
187 
188 }

 

 

3.2 计算最短路径

3.2.1 索引优先队列

  1 package study.algorithm.base;
  2 
  3 import java.util.Iterator;
  4 import java.util.NoSuchElementException;
  5 
  6 /**
  7  * 索引最小优先级队列
  8  *
  9  * @param <Key>
 10  */
 11 public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
 12     /**
 13      * 元素数量上限
 14      */
 15     private int maxN;
 16     /**
 17      * 元素数量
 18      */
 19     private int n;
 20     /**
 21      * 索引二叉堆(元素=顶点v,对应keys[v]):pq[0]代表原点,其它顶点从pq[1]开始插入
 22      */
 23     private int[] pq;
 24     /**
 25      * 标记索引为i的元素在二叉堆中的位置。pq的反转数组(qp[index]=i):qp[pq[i]] = pq[qp[i]] = i
 26      */
 27     private int[] qp;
 28 
 29     /**
 30      * 元素有序数组(按照pq的索引赋值)
 31      */
 32     private Key[] keys;
 33 
 34     /**
 35      * 初始化一个空索引优先队列,索引范围:0 ~ maxN-1
 36      *
 37      * @param  maxN the keys on this priority queue are index from {@code 0}
 38      *         {@code maxN - 1}
 39      * @throws IllegalArgumentException if {@code maxN < 0}
 40      */
 41     public IndexMinPQ(int maxN) {
 42         if (maxN < 0) throw new IllegalArgumentException();
 43         this.maxN = maxN;
 44         // 初始有0个元素
 45         n = 0;
 46         // 初始化键数组长度为maxN + 1
 47         keys = (Key[]) new Comparable[maxN + 1];
 48         // 初始化"键值对"数组长度为maxN + 1
 49         pq   = new int[maxN + 1];
 50         // 初始化"值键对"数组长度为maxN + 1
 51         qp   = new int[maxN + 1];
 52         // 遍历给"值键对"数组赋值-1,后续只要!=-1,即包含i
 53         for (int i = 0; i <= maxN; i++)
 54             qp[i] = -1;
 55     }
 56 
 57     /**
 58      * Returns true if this priority queue is empty.
 59      *
 60      * @return {@code true} if this priority queue is empty;
 61      *         {@code false} otherwise
 62      */
 63     public boolean isEmpty() {
 64         return n == 0;
 65     }
 66 
 67     /**
 68      * Is {@code i} an index on this priority queue?
 69      *
 70      * @param  i an index
 71      * @return {@code true} if {@code i} is an index on this priority queue;
 72      *         {@code false} otherwise
 73      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
 74      */
 75     public boolean contains(int i) {
 76         validateIndex(i);
 77         return qp[i] != -1;
 78     }
 79 
 80     /**
 81      * Returns the number of keys on this priority queue.
 82      *
 83      * @return the number of keys on this priority queue
 84      */
 85     public int size() {
 86         return n;
 87     }
 88 
 89     /**
 90      * 插入一个元素,将元素key关联索引i
 91      *
 92      * @param  i an index
 93      * @param  key the key to associate with index {@code i}
 94      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
 95      * @throws IllegalArgumentException if there already is an item associated
 96      *         with index {@code i}
 97      */
 98     public void insert(int i, Key key) {
 99         validateIndex(i);
100         if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
101         // 元素个数+1
102         n++;
103         // 索引为i的二叉堆位置为n
104         qp[i] = n;
105         // 二叉堆底部插入新元素,值=i
106         pq[n] = i;
107         // 索引i对应的元素赋值
108         keys[i] = key;
109         // 二叉堆中,上浮最后一个元素(小值上浮)
110         swim(n);
111     }
112 
113     /**
114      * 返回最小元素的索引
115      *
116      * @return an index associated with a minimum key
117      * @throws NoSuchElementException if this priority queue is empty
118      */
119     public int minIndex() {
120         if (n == 0) throw new NoSuchElementException("Priority queue underflow");
121         return pq[1];
122     }
123 
124     /**
125      * 返回最小元素(key)
126      *
127      * @return a minimum key
128      * @throws NoSuchElementException if this priority queue is empty
129      */
130     public Key minKey() {
131         if (n == 0) throw new NoSuchElementException("Priority queue underflow");
132         return keys[pq[1]];
133     }
134 
135     /**
136      * 删除最小值key,并返回最小值
137      *
138      * @return an index associated with a minimum key
139      * @throws NoSuchElementException if this priority queue is empty
140      */
141     public int delMin() {
142         if (n == 0) throw new NoSuchElementException("Priority queue underflow");
143         // pq[1]即为索引最小值
144         int min = pq[1];
145         // 交换第一个元素和最后一个元素
146         exch(1, n--);
147         // 把新换来的第一个元素下沉
148         sink(1);
149         // 校验下沉后,最后一个元素是最小值
150         assert min == pq[n+1];
151         // 恢复初始值,-1即代表该元素已删除
152         qp[min] = -1;        // delete
153         // 方便垃圾回收
154         keys[min] = null;
155         // 最后一个元素(索引)赋值-1
156         pq[n+1] = -1;        // not needed
157         return min;
158     }
159 
160     /**
161      * Returns the key associated with index {@code i}.
162      *
163      * @param  i the index of the key to return
164      * @return the key associated with index {@code i}
165      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
166      * @throws NoSuchElementException no key is associated with index {@code i}
167      */
168     public Key keyOf(int i) {
169         validateIndex(i);
170         if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
171         else return keys[i];
172     }
173 
174     /**
175      * Change the key associated with index {@code i} to the specified value.
176      *
177      * @param  i the index of the key to change
178      * @param  key change the key associated with index {@code i} to this key
179      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
180      * @throws NoSuchElementException no key is associated with index {@code i}
181      */
182     public void changeKey(int i, Key key) {
183         validateIndex(i);
184         if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
185         keys[i] = key;
186         swim(qp[i]);
187         sink(qp[i]);
188     }
189 
190     /**
191      * Change the key associated with index {@code i} to the specified value.
192      *
193      * @param  i the index of the key to change
194      * @param  key change the key associated with index {@code i} to this key
195      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
196      * @deprecated Replaced by {@code changeKey(int, Key)}.
197      */
198     @Deprecated
199     public void change(int i, Key key) {
200         changeKey(i, key);
201     }
202 
203     /**
204      * 减小索引i对应的值为key
205      * 更新:
206      * 1.元素数组keys[]
207      * 2.小顶二叉堆pq[]
208      *
209      * @param  i the index of the key to decrease
210      * @param  key decrease the key associated with index {@code i} to this key
211      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
212      * @throws IllegalArgumentException if {@code key >= keyOf(i)}
213      * @throws NoSuchElementException no key is associated with index {@code i}
214      */
215     public void decreaseKey(int i, Key key) {
216         validateIndex(i);
217         if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
218         // key 值一样,报错
219         if (keys[i].compareTo(key) == 0)
220             throw new IllegalArgumentException("Calling decreaseKey() with a key equal to the key in the priority queue");
221         // key比当前值大,报错
222         if (keys[i].compareTo(key) < 0)
223             throw new IllegalArgumentException("Calling decreaseKey() with a key strictly greater than the key in the priority queue");
224         // key比当前值小,把key赋值进去
225         keys[i] = key;
226         // 小值上浮(qp[i]=索引i在二叉堆pq[]中的位置)
227         swim(qp[i]);
228     }
229 
230     /**
231      * Increase the key associated with index {@code i} to the specified value.
232      *
233      * @param  i the index of the key to increase
234      * @param  key increase the key associated with index {@code i} to this key
235      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
236      * @throws IllegalArgumentException if {@code key <= keyOf(i)}
237      * @throws NoSuchElementException no key is associated with index {@code i}
238      */
239     public void increaseKey(int i, Key key) {
240         validateIndex(i);
241         if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
242         if (keys[i].compareTo(key) == 0)
243             throw new IllegalArgumentException("Calling increaseKey() with a key equal to the key in the priority queue");
244         if (keys[i].compareTo(key) > 0)
245             throw new IllegalArgumentException("Calling increaseKey() with a key strictly less than the key in the priority queue");
246         keys[i] = key;
247         sink(qp[i]);
248     }
249 
250     /**
251      * Remove the key associated with index {@code i}.
252      *
253      * @param  i the index of the key to remove
254      * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
255      * @throws NoSuchElementException no key is associated with index {@code i}
256      */
257     public void delete(int i) {
258         validateIndex(i);
259         if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
260         int index = qp[i];
261         exch(index, n--);
262         swim(index);
263         sink(index);
264         keys[i] = null;
265         qp[i] = -1;
266     }
267 
268     // throw an IllegalArgumentException if i is an invalid index
269     private void validateIndex(int i) {
270         if (i < 0) throw new IllegalArgumentException("index is negative: " + i);
271         if (i >= maxN) throw new IllegalArgumentException("index >= capacity: " + i);
272     }
273 
274    /***************************************************************************
275     * General helper functions.
276     ***************************************************************************/
277     private boolean greater(int i, int j) {
278         return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
279     }
280 
281     private void exch(int i, int j) {
282         int swap = pq[i];
283         pq[i] = pq[j];
284         pq[j] = swap;
285         qp[pq[i]] = i;
286         qp[pq[j]] = j;
287     }
288 
289 
290    /***************************************************************************
291     * Heap helper functions.
292     ***************************************************************************/
293     private void swim(int k) {
294         // 如果父节点值比当前节点值大,交换,父节点作为当前节点,轮询。即小值上浮。
295         while (k > 1 && greater(k/2, k)) {
296             exch(k, k/2);
297             k = k/2;
298         }
299     }
300 
301     private void sink(int k) {
302         while (2*k <= n) {
303             int j = 2*k;
304             if (j < n && greater(j, j+1)) j++;
305             if (!greater(k, j)) break;
306             exch(k, j);
307             k = j;
308         }
309     }
310 
311 
312    /***************************************************************************
313     * Iterators.
314     ***************************************************************************/
315 
316     /**
317      * Returns an iterator that iterates over the keys on the
318      * priority queue in ascending order.
319      * The iterator doesn't implement {@code remove()} since it's optional.
320      *
321      * @return an iterator that iterates over the keys in ascending order
322      */
323     @Override
324     public Iterator<Integer> iterator() { return new HeapIterator(); }
325 
326     private class HeapIterator implements Iterator<Integer> {
327         // create a new pq
328         private IndexMinPQ<Key> copy;
329 
330         // add all elements to copy of heap
331         // takes linear time since already in heap order so no keys move
332         public HeapIterator() {
333             copy = new IndexMinPQ<Key>(pq.length - 1);
334             for (int i = 1; i <= n; i++)
335                 copy.insert(pq[i], keys[pq[i]]);
336         }
337 
338         @Override
339         public boolean hasNext()  { return !copy.isEmpty();                     }
340         @Override
341         public void remove()      { throw new UnsupportedOperationException();  }
342 
343         @Override
344         public Integer next() {
345             if (!hasNext()) throw new NoSuchElementException();
346             return copy.delMin();
347         }
348     }
349 
350 
351     /**
352      * Unit tests the {@code IndexMinPQ} data type.
353      *
354      * @param args the command-line arguments
355      */
356     public static void main(String[] args) {
357         // insert a bunch of strings
358         String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
359 
360         IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
361         for (int i = 0; i < strings.length; i++) {
362             pq.insert(i, strings[i]);
363         }
364 
365         // delete and print each key
366         while (!pq.isEmpty()) {
367             int i = pq.delMin();
368             StdOut.println(i + " " + strings[i]);
369         }
370         StdOut.println();
371 
372         // reinsert the same strings
373         for (int i = 0; i < strings.length; i++) {
374             pq.insert(i, strings[i]);
375         }
376 
377         // print each key using the iterator
378         for (int i : pq) {
379             StdOut.println(i + " " + strings[i]);
380         }
381         while (!pq.isEmpty()) {
382             pq.delMin();
383         }
384 
385     }
386 }

 

3.2.2 最短路径

  1 package study.algorithm.graph;
  2 
  3 import study.algorithm.base.In;
  4 import study.algorithm.base.IndexMinPQ;
  5 import study.algorithm.base.Stack;
  6 import study.algorithm.base.StdOut;
  7 
  8 /***
  9  * @Description 边权重非负的加权有向图的单起点最短路径树
 10  * @author denny.zhang
 11  * @date 2020/4/23 11:29 上午
 12  */
 13 public class DijkstraSP {
 14 
 15     /**
 16      * 最短路径数组,元素:到所有顶点的最短路径
 17      */
 18     private double[] distTo;
 19 
 20     /**
 21      * 有向边数组:最短路径最后一条边数组
 22      */
 23     private DirectedEdge[] edgeTo;
 24 
 25     /**
 26      * 顶点作为下标,索引最小优先级队列
 27      */
 28     private IndexMinPQ<Double> pq;
 29 
 30     /**
 31      * 计算从原点S 到 其它所有顶点 的"最短路径" 边权重 图
 32      *
 33      * @param  G the edge-weighted digraph 边权重图
 34      * @param  s the source vertex 原点
 35      * @throws IllegalArgumentException if an edge weight is negative
 36      * @throws IllegalArgumentException unless {@code 0 <= s < V}
 37      */
 38     public DijkstraSP(EdgeWeightedDigraph G, int s) {
 39         // 负权重校验
 40         for (DirectedEdge e : G.edges()) {
 41             if (e.weight() < 0) {
 42                 throw new IllegalArgumentException("edge " + e + " has negative weight");
 43             }
 44         }
 45         // 最短路径数组长度=顶点个数
 46         distTo = new double[G.V()];
 47         // 构造长度为顶点总数的最短路径边数组
 48         edgeTo = new DirectedEdge[G.V()];
 49         // 校验原点值
 50         validateVertex(s);
 51         // 初始化所有顶点的路径为无穷大
 52         for (int v = 0; v < G.V(); v++) {
 53             distTo[v] = Double.POSITIVE_INFINITY;
 54         }
 55         // 初始化到原点最小路径为0
 56         distTo[s] = 0.0;
 57 
 58         // 构造一个长度为 顶点总数的 索引最小优先队列
 59         pq = new IndexMinPQ<Double>(G.V());
 60         // 把原点插入,路径为0
 61         pq.insert(s, distTo[s]);
 62         // 只要队列不空(从上往下,顺序遍历一遍pq[]),
 63         while (!pq.isEmpty()) {
 64             // 删除最小key(即pq[1]),并返回最小值(顶点)
 65             int v = pq.delMin();
 66             // 遍历顶点v的邻接表,每一条边
 67             for (DirectedEdge e : G.adj(v)) {
 68                 // 放松边
 69                 relax(e);
 70             }
 71         }
 72 
 73         // 校验
 74         assert check(G, s);
 75     }
 76 
 77     /**
 78      * 放松并更新pq
 79      * @param e
 80      */
 81     private void relax(DirectedEdge e) {
 82         // 起点、终点
 83         int v = e.from(), w = e.to();
 84         // 如果原点到终点w的距离 > 原点到起点v的距离+边权重  说明原点到w松弛了
 85         if (distTo[w] > distTo[v] + e.weight()) {
 86             // 最新距离
 87             distTo[w] = distTo[v] + e.weight();
 88             // 到终点w的边赋值为新边
 89             edgeTo[w] = e;
 90             // 如果优先队列已经包含终点w
 91             if (pq.contains(w)) {
 92                 // 比较下标为w的key如果>当前路径(即当前值比队列中值小),重新排序
 93                 pq.decreaseKey(w, distTo[w]);
 94             } else {
 95                 // 不包含,插入并排序
 96                 pq.insert(w, distTo[w]);
 97             }
 98         }
 99     }
100 
101     /**
102      * s->v的最短路径
103      * @param  v the destination vertex
104      * @return the length of a shortest path from the source vertex {@code s} to vertex {@code v};
105      *         {@code Double.POSITIVE_INFINITY} if no such path
106      * @throws IllegalArgumentException unless {@code 0 <= v < V}
107      */
108     public double distTo(int v) {
109         validateVertex(v);
110         return distTo[v];
111     }
112 
113     /**
114      * s->v是否可达
115      *
116      * @param  v the destination vertex
117      * @return {@code true} if there is a path from the source vertex
118      *         {@code s} to vertex {@code v}; {@code false} otherwise
119      * @throws IllegalArgumentException unless {@code 0 <= v < V}
120      */
121     public boolean hasPathTo(int v) {
122         validateVertex(v);
123         return distTo[v] < Double.POSITIVE_INFINITY;
124     }
125 
126     /**
127      * s->v的最短可迭代边(1->2->3)
128      *
129      * @param  v the destination vertex
130      * @return a shortest path from the source vertex {@code s} to vertex {@code v}
131      *         as an iterable of edges, and {@code null} if no such path
132      * @throws IllegalArgumentException unless {@code 0 <= v < V}
133      */
134     public Iterable<DirectedEdge> pathTo(int v) {
135         validateVertex(v);
136         if (!hasPathTo(v)) {
137             return null;
138         }
139         // 可迭代有向边栈
140         Stack<DirectedEdge> path = new Stack<DirectedEdge>();
141         // e是顶点v的最短路径树的最后一条边,沿着边往上追溯上一个顶点 3->2->1
142         for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
143             // 压栈
144             path.push(e);
145         }
146         return path;
147     }
148 
149 
150     // check optimality conditions:
151     // (i) for all edges e:            distTo[e.to()] <= distTo[e.from()] + e.weight()
152     // (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight()
153     private boolean check(EdgeWeightedDigraph G, int s) {
154 
155         // 校验边权重不为负值
156         for (DirectedEdge e : G.edges()) {
157             if (e.weight() < 0) {
158                 System.err.println("negative edge weight detected");
159                 return false;
160             }
161         }
162 
163         // 校验到顶点的路径为0且到顶点的边为空
164         if (distTo[s] != 0.0 || edgeTo[s] != null) {
165             System.err.println("distTo[s] and edgeTo[s] inconsistent");
166             return false;
167         }
168         // 遍历顶点
169         for (int v = 0; v < G.V(); v++) {
170             // 起点跳过
171             if (v == s) {
172                 continue;
173             }
174             // 到顶点v的最后一条边为空(不可达) 且 到顶点v的最短路径不是无穷大(即有值)两者冲突
175             if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
176                 System.err.println("distTo[] and edgeTo[] inconsistent");
177                 return false;
178             }
179         }
180 
181         // 校验所有边非松弛
182         for (int v = 0; v < G.V(); v++) {
183             // 遍历顶点v的邻接边
184             for (DirectedEdge e : G.adj(v)) {
185                 int w = e.to();
186                 // 校验松弛
187                 if (distTo[v] + e.weight() < distTo[w]) {
188                     System.err.println("edge " + e + " not relaxed");
189                     return false;
190                 }
191             }
192         }
193 
194         // 校验最短路径树:满足 distTo[w] == distTo[v] + e.weight()
195         for (int w = 0; w < G.V(); w++) {
196             // 跳过不可达顶点
197             if (edgeTo[w] == null) {
198                 continue;
199             }
200             // 最后一条边
201             DirectedEdge e = edgeTo[w];
202             // 起点
203             int v = e.from();
204             //终点
205             if (w != e.to()) {
206                 return false;
207             }
208             // 校验:最短路劲树,起点路径+权重=终点路径
209             if (distTo[v] + e.weight() != distTo[w]) {
210                 System.err.println("edge " + e + " on shortest path not tight");
211                 return false;
212             }
213         }
214         return true;
215     }
216 
217     // throw an IllegalArgumentException unless {@code 0 <= v < V}
218     private void validateVertex(int v) {
219         int V = distTo.length;
220         if (v < 0 || v >= V) {
221             throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
222         }
223     }
224 
225     /**
226      * Unit tests the {@code DijkstraSP} data type.
227      *
228      * @param args the command-line arguments
229      */
230     public static void main(String[] args) {
231         // 图文件名称
232         In in = new In(args[0]);
233         // 构造边权重有向图
234         EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
235         // 顶点
236         int s = Integer.parseInt(args[1]);
237 
238         // 计算最短路径
239         DijkstraSP sp = new DijkstraSP(G, s);
240 
241         // 遍历所有顶点
242         for (int t = 0; t < G.V(); t++) {
243             // 可达
244             if (sp.hasPathTo(t)) {
245                 // 原点到t的路径 长度
246                 StdOut.printf("%d to %d (%.2f)  ", s, t, sp.distTo(t));
247                 // 原点到t的路径图
248                 for (DirectedEdge e : sp.pathTo(t)) {
249                     StdOut.print(e + "   ");
250                 }
251                 // 换行
252                 StdOut.println();
253             }
254             // 不可达
255             else {
256                 StdOut.printf("%d to %d         no path\n", s, t);
257             }
258         }
259     }
260 
261 }

 

 四、测试结果

4.1 测试准备

本地生存一个文件 tinyEWD.txt,内容如下:

8
15
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

4.2 测试

本地运行DijkstraSP,配置运行参数,以idea为例:第一个入参是文件地址,第二个参数代表原点是0,计算从原点(顶点0)到 其它所有顶点 的”最短路径” 边权重 图:

运行的最短路径,结果如下: