1.算法讲解

作者以图表流程图的方式来讲解无权图的最短路径算法。

请参看此链接：
processon分享链接

2.代码示例

/**
 * @description： 无权图最短路径
 * @Author MRyan
 * @Version 1.0
 */
public class PathUnweighted {

    public static void main(String[] args) {
        // 节点总数
        int vertexSize = 8;

        // 邻接表模型
        List<List<Integer>> adj = new ArrayList<>(vertexSize);
        for (int i = 0; i < vertexSize; i++) {
            adj.add(new ArrayList<>());
        }

        // 添加节点和节点之间的边
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 3);
        addEdge(adj, 1, 2);
        addEdge(adj, 3, 4);
        addEdge(adj, 3, 7);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        addEdge(adj, 4, 7);
        addEdge(adj, 5, 6);
        addEdge(adj, 6, 7);

        // 求节点0到节点7之间的最短路径
        int source = 0, dest = 7;

        // 打印节点0到节点7之间的最短路径
        printShortestDistance(adj, source, dest, vertexSize);
    }

    /**
     * 添加节点和节点之间的边
     *
     * @param adj              邻接表
     * @param vertexIndexStart 起点节点
     * @param vertexIndexEnd   终止节点
     */
    private static void addEdge(List<List<Integer>> adj, int vertexIndexStart, int vertexIndexEnd) {
        adj.get(vertexIndexStart).add(vertexIndexEnd);
        adj.get(vertexIndexEnd).add(vertexIndexStart);
    }


    /**
     * 打印最短距离和路径
     *
     * @param adj        邻接表
     * @param source     起始节点
     * @param dest       到达节点
     * @param vertexSize
     */
    private static void printShortestDistance(List<List<Integer>> adj, int source, int dest, int vertexSize) {
        // 前节点记录路径
        int[] pred = new int[vertexSize];
        // 从某节点出发到该节点的最短路径集合
        int[] dist = new int[vertexSize];

        if (!BFS(adj, source, dest, vertexSize, pred, dist)) {
            System.out.println("Given source and destination are not connected");
            return;
        }

        // LinkedList to store path
        LinkedList<Integer> path = new LinkedList<>();
        int crawl = dest;
        path.add(crawl);
        while (true) {
            int temp = pred[crawl];
            if (temp == -1) break;
            path.add(temp);
            crawl = temp;
        }

        // 打印最短距离
        System.out.println("Shortest path length is -> " + dist[dest]);

        // 打印最短距离路径
        System.out.print("Path is -> ");
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i) + " ");
        }
    }

    /**
     * BFS遍历
     *
     * @param adj
     * @param source
     * @param dest
     * @param vertexSize
     * @param pred
     * @param dist
     * @return
     */
    private static boolean BFS(List<List<Integer>> adj, int source,
                               int dest, int vertexSize, int[] pred, int[] dist) {
        // 队列
        LinkedList<Integer> queue = new LinkedList<>();

        // 是否访问过
        boolean[] visited = new boolean[vertexSize];

        // 初始化状态
        for (int i = 0; i < vertexSize; i++) {
            visited[i] = false;
            dist[i] = Integer.MAX_VALUE;
            pred[i] = -1;
        }

        // 准备工作
        visited[source] = true;
        dist[source] = 0;
        queue.add(source);

        // bfs Algorithm
        // 开始循环，每次循环开始时先查看队列
        while (!queue.isEmpty()) {
            // 取出队列中第一个元素
            int u = queue.remove();
            for (int i = 0; i < adj.get(u).size(); i++) {
                Integer index = adj.get(u).get(i);
                if (!visited[index]) {
                    visited[index] = true;
                    dist[index] = dist[u] + 1;
                    pred[index] = u;
                    queue.add(index);

                    // stopping condition (when we find our destination)
                    if (index == dest)
                        return true;
                }
            }
        }
        return false;
    }

}

参考

https://www.geeksforgeeks.org/shortest-path-unweighted-graph/

作者：MRyan

本文采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
转载时请注明本文出处及文章链接。本文链接：https://wormholestack.com/archives/610/