1 單點(diǎn)最短路徑

單點(diǎn)最短路徑。 給定一幅圖和一個(gè)起點(diǎn)s，回答“從s到給定目的頂點(diǎn)v是否存在一條路徑？如果有，找出其中最短的那條（所含邊數(shù)最少）?！暗阮愃茊栴}。

深度優(yōu)先搜索在這個(gè)問題上沒有什么作為，因?yàn)樗闅v整個(gè)圖的順序和找出最短路徑的目標(biāo)沒有任何關(guān)系。相比之下，廣度優(yōu)先搜索正好可以解決這個(gè)問題。

分析：

• 要找的從s到v的最短路徑，從s開始，在所有由一條邊就可以到達(dá)的頂點(diǎn)中尋找v，找到標(biāo)記結(jié)束。
• 如果沒有找到，我們繼續(xù)在于s距離2條邊的頂點(diǎn)中查找v，如此一直進(jìn)行。
• 最后也沒有找到，那么說明s到給定頂點(diǎn)v不存在路徑，此圖為非連通圖。

結(jié)構(gòu)選擇：

• 廣度優(yōu)先搜索中，我們希望按照與起點(diǎn)的距離順序遍歷所有頂點(diǎn)，所以我們選擇隊(duì)列（先入先出）。

2 廣度優(yōu)先搜索實(shí)現(xiàn)

實(shí)現(xiàn)代碼如下：

package com.gaogzhen.datastructure.graph.undirected;import edu.princeton.cs.algs4.*;/*** 最短路徑算法* @author: Administrator* @createTime: 2023/03/07 21:04*/
public class BreadthFirstDirectedPaths {private static final int INFINITY = Integer.MAX_VALUE;/*** 標(biāo)記頂點(diǎn)是否與起點(diǎn)連通*/private boolean[] marked;/*** 表示頂點(diǎn)到與該頂點(diǎn)連通的頂點(diǎn)間最短路徑*/private int[] edgeTo;/*** 頂點(diǎn)到起點(diǎn)之間的邊數(shù)*/private int[] distTo;/*** 計(jì)算從指定頂點(diǎn)到起點(diǎn)最短路徑* @param G 無向圖* @param s 起點(diǎn)* @throws IllegalArgumentException unless {@code 0 <= v < V}*/public BreadthFirstDirectedPaths(Graph G, int s) {marked = new boolean[G.V()];distTo = new int[G.V()];edgeTo = new int[G.V()];for (int v = 0; v < G.V(); v++) {distTo[v] = INFINITY;edgeTo[v] = -1;}validateVertex(s);bfs(G, s);}/*** 計(jì)算多個(gè)起點(diǎn)到指定頂點(diǎn)之間的最短路徑* @param G 無向圖* @param sources 多個(gè)起點(diǎn)集合* @throws IllegalArgumentException if {@code sources} is {@code null}* @throws IllegalArgumentException unless each vertex {@code v} in*         {@code sources} satisfies {@code 0 <= v < V}*/public BreadthFirstDirectedPaths(Graph G, Iterable<Integer> sources) {marked = new boolean[G.V()];distTo = new int[G.V()];edgeTo = new int[G.V()];for (int v = 0; v < G.V(); v++) {distTo[v] = INFINITY;edgeTo[v] = -1;}validateVertices(sources);bfs(G, sources);}/*** 廣度優(yōu)先搜索從指定頂點(diǎn)到起點(diǎn)最短路徑* @param G 無向圖* @param s 起點(diǎn)*/private void bfs(Graph G, int s) {Queue<Integer> q = new Queue<Integer>();marked[s] = true;distTo[s] = 0;q.enqueue(s);while (!q.isEmpty()) {int v = q.dequeue();for (int w : G.adj(v)) {if (!marked[w]) {edgeTo[w] = v;distTo[w] = distTo[v] + 1;marked[w] = true;q.enqueue(w);}}}}// BFS from multiple sourcesprivate void bfs(Graph G, Iterable<Integer> sources) {Queue<Integer> q = new Queue<Integer>();for (int s : sources) {marked[s] = true;distTo[s] = 0;q.enqueue(s);}while (!q.isEmpty()) {int v = q.dequeue();for (int w : G.adj(v)) {if (!marked[w]) {edgeTo[w] = v;distTo[w] = distTo[v] + 1;marked[w] = true;q.enqueue(w);}}}}/*** 起點(diǎn)s與指定頂點(diǎn)v之間是否有路徑（連通）* @param v the vertex* @return {@code true} if there is a directed path, {@code false} otherwise* @throws IllegalArgumentException unless {@code 0 <= v < V}*/public boolean hasPathTo(int v) {validateVertex(v);return marked[v];}/*** 返回指定頂點(diǎn)v到起點(diǎn)直接的最短路徑（邊數(shù)）}?* @param v the vertex* @return the number of edges in such a shortest path*         (or {@code Integer.MAX_VALUE} if there is no such path)* @throws IllegalArgumentException unless {@code 0 <= v < V}*/public int distTo(int v) {validateVertex(v);return distTo[v];}/*** 返回指定頂點(diǎn)v到起點(diǎn)直接的最短路徑，沒有返回null* @param v the vertex* @return the sequence of vertices on a shortest path, as an Iterable* @throws IllegalArgumentException unless {@code 0 <= v < V}*/public Iterable<Integer> pathTo(int v) {validateVertex(v);if (!hasPathTo(v)) return null;Stack<Integer> path = new Stack<Integer>();int x;for (x = v; distTo[x] != 0; x = edgeTo[x])path.push(x);path.push(x);return path;}// throw an IllegalArgumentException unless {@code 0 <= v < V}private void validateVertex(int v) {int V = marked.length;if (v < 0 || v >= V)throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));}// throw an IllegalArgumentException if vertices is null, has zero vertices,// or has a vertex not between 0 and V-1private void validateVertices(Iterable<Integer> vertices) {if (vertices == null) {throw new IllegalArgumentException("argument is null");}int V = marked.length;int count = 0;for (Integer v : vertices) {count++;if (v == null) {throw new IllegalArgumentException("vertex is null");}validateVertex(v);}if (count == 0) {throw new IllegalArgumentException("zero vertices");}}
}

隊(duì)列保存所有已被標(biāo)記但其鄰接表未被檢查過的頂點(diǎn)。先將起點(diǎn)加入隊(duì)列，然后重復(fù)一下步驟知道隊(duì)列為空。

• 取出隊(duì)列中的下一個(gè)頂點(diǎn)v并標(biāo)記它。
• 將與v相鄰的所有未被標(biāo)記過的頂點(diǎn)加入隊(duì)列。

說明：

• edgeTo[]數(shù)組結(jié)果，也是一棵用父鏈接表示的根結(jié)點(diǎn)為s的樹
  • 多起點(diǎn)中，則以各自起點(diǎn)為根結(jié)點(diǎn)的樹組成的森林。
• distTo[]表示到起點(diǎn)的路徑長度，即邊數(shù)。代碼distTo[w] = distTo[v] + 1;當(dāng)前頂點(diǎn)路徑長度為其父頂點(diǎn)路徑長度+1，起點(diǎn)為0。
• 與算法第四版不同的地方只是在初始化edgeTo為-1表示根結(jié)點(diǎn)；算法第四版默認(rèn)都是0。

以之前無向圖（6個(gè)頂點(diǎn)，8條邊）為例單起點(diǎn)搜索索引起點(diǎn)為0（單起點(diǎn)的路徑結(jié)果：

多起點(diǎn)（0,2）搜索結(jié)果如下圖所示：

多起點(diǎn)搜索很少用到，一般情況下我們討論最短路徑默認(rèn)為單點(diǎn)最短路徑。

3 總結(jié)

命題B。對于從s可達(dá)的任意頂點(diǎn)v，廣度優(yōu)先搜索都能找到一條從s到v的最短路徑（沒有其他從s到v的路徑所含有的邊比這條路徑少。

證明：由歸納易得隊(duì)列總是包含林哥或者多個(gè)到起點(diǎn)的距離為k的頂點(diǎn)，之后是零個(gè)或者多個(gè)到起點(diǎn)為k+1的頂點(diǎn)，k為整數(shù)，起始值為0.這意味著頂點(diǎn)是按照它們和s的距離順序加入或者離開隊(duì)列。從頂點(diǎn)v加入隊(duì)列到它離開隊(duì)列之前，不可能找出到v的更短路徑，而在v離開隊(duì)列之后發(fā)現(xiàn)的所有能夠到達(dá)v的路徑都不可能短于v在樹中的路徑長度。

命題B（續(xù)）。廣度優(yōu)先搜索所需的時(shí)間在最壞情況下和V+E成正比。

證明：廣度優(yōu)先搜索標(biāo)記所有與s連通的頂點(diǎn)所需的時(shí)間與它們的度數(shù)之和成正比。如果圖是連通的，這個(gè)和就是所有頂點(diǎn)的度數(shù)之和，也就是2E。

廣度優(yōu)先搜索也可以解決單點(diǎn)連通問題，它檢查所有與起點(diǎn)連通的頂點(diǎn)和邊的方法取決于查找的能力。代碼如下：

private void bfs(Graph G, int s) {Queue<Integer> q = new Queue<Integer>();marked[s] = true;q.enqueue(s);while (!q.isEmpty()) {int v = q.dequeue();for (int w : G.adj(v)) {if (!marked[w]) {marked[w] = true;q.enqueue(w);}}}
}

后記

如果小伙伴什么問題或者指教，歡迎交流。

?QQ:806797785

??源代碼倉庫地址：https://gitee.com/gaogzhen/algorithm

參考鏈接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;謝路云譯.算法：第4版[M].北京：人民郵電出版社，2012.10.p344-348.