JAVA广度优先实现最短路径问题

￡神魔★判官ぃ 2022-06-14 01:49 269阅读 0赞

最短路径分为`点到点最短路径`和`源点到其他点的最短路径`问题，下面给出`广度优先BFS算法`的实现。

# **一、点到点** #

## **1.1 问题描述** ##

这里采用迷宫问题来举例。求从起点到终点的最短路径，采用广度优先的顺序，首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径。  
由于顶点的最短路径的求解顺序 是一个广度优先的顺序，因此需要一个辅助队列。具体步骤如下：  
①从起点开始，先将其加入队列，设置距离为0；  
②从队列首端取出位置，将从这个位置能够到达的位置加入队列，并且让这些位置的距离为上一个位置的距离加上1；  
③循环2直到将终点添加到队列中，这说明我们已经找到了路径；  
在这个过程中，每次处理的位置所对应的距离是严格递增的，因此一旦找到终点，当时的距离就是最短距离。  
由此可见，迷宫问题是一个无向无权图。

## **1.2 算法实现** ##

import java.awt.Point;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Maze { 
        static int M, N, dx, dy, gx, gy;
        static char[][] a;
        static int[][] deep;
    
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            System.out.println("请输入迷宫的行数：");
            M = s.nextInt();
            System.out.println("请输入迷宫的列数：");
            N = s.nextInt();
            a = new char[M][N];
            deep = new int[M][N];
            System.out.println("请输入迷宫矩阵(起点为'm',终点为'e',墙壁为'1'，可行路径为'0')：");
            for (int i = 0; i < M; i++) {
                a[i] = s.next().toCharArray();
            }
    
            for (int i = 0; i < M; i++)
                for (int j = 0; j < N; j++) {
                    if (a[i][j] == 'm') {
                        dx = i;
                        dy = j;
                    }
                    if (a[i][j] == 'e') {
                        gx = i;
                        gy = j;
                    }
                }
            int len = bfs();
            System.out.println("从起点到终点的最短路径为：" + len);
        }
    
        private static int bfs() {
            Queue<Point> q = new LinkedList<Point>();
            int[] tx = { -1, 1, 0, 0 };
            int[] ty = { 0, 0, 1, -1 };
            q.offer(new Point(dx, dy));
    
            for (int i = 0; i < M; i++)
                for (int j = 0; j < N; j++)
                    deep[i][j] = -1;
            deep[dx][dy] = 0;
    
            while (q.size() > 0) {
                Point p = q.poll();
                if (p.x == gx && p.y == gy)
                    break;
                for (int i = 0; i < 4; i++) {
                    int x = p.x + tx[i];
                    int y = p.y + ty[i];
                    if (x >= 0 && x < M && y >= 0 && y < N && a[x][y] != '1'
                            && deep[x][y] == -1) {
                        deep[x][y] = deep[p.x][p.y] + 1;
                        q.offer(new Point(x, y));
                    }
                }
            }
            return deep[gx][gy];
        }
    
    }

## **1.3 算法测试** ##

测试数据为10\*10矩阵;  
矩阵为：  
1111111111  
1m01000101  
1001000101  
1000011001  
1011100001  
1000100001  
1010001001  
1011101101  
11000000e1  
1111111111

**运行结果为：**  
![这里写图片描述][SouthEast]

# **二、源点到其他点** #

## **2.1 问题描述** ##

源点的最短路径距离为0，从源点开始，采用广度优先的顺序，首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径。  
由于顶点的最短路径的求解顺序、是一个广度优先的顺序，因此需要一个辅助队列。初始时，将源点的最短路径距离设置为0，将源点入队列。  
然后，在一个while循环中，从队列中弹出顶点，遍历该顶点的邻接点，若该邻接点的距离未被更新过（表示该邻接点未被访问过），更新邻接点的最短路径距离为该顶点的距离加上1，并将所有的邻接点入队列。  
这里采用的图为有向无权图。

## **2.2 算法实现** ##

//边类：
    class Edge {
    
        String to;//边指向的节点
        public String getTo() {
            return to;
        }
        public void setTo(String to) {
            this.to = to;
        }
        Edge nextEdge;//具有同一起点的下一条边
        public Edge(String to) {
            this.to = to;
            this.nextEdge = null;
    
        }
    
    }

//点类：
    public class Vertex { 
    
        String from;// 边的起点
        int pathLength = 0;//路径长度
        boolean isVisted = false;
        int indegree;// 每个顶点的入度
        Edge first;// 以from为起点的第一条边
    
        public boolean getIsVisted() {
            return isVisted;
        }
    
        public void setIsVisted(boolean isVisted) {
            this.isVisted = isVisted;
        }
    
        public String getFrom() {
            return from;
        }
    
        public void setFrom(String from) {
            this.from = from;
        }
    
        public Vertex(String from) {
            this.from = from;
            first = null;
            this.indegree = 0;
        }
    
        public int getPathlength() {
            return pathLength;
        }
    
        public void setPathlength(int counter) {
            pathLength = counter;
        }
    
    }

//图类：
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Graph { 
    
        public Vertex[] v;
        public Edge[] e;
        public int edgeNumber;
        public int vertexNumber;
    
        // 根据输入建立一个有向图
        public void buildGraph() {
            Scanner s = new Scanner(System.in);
            System.out.println("请输入有向图的顶点数：");
            vertexNumber = s.nextInt();
            System.out.println("请输入有向图的边数：");
            edgeNumber = s.nextInt();
    
            // 建立顶点数组
            v = new Vertex[vertexNumber];
            e = new Edge[edgeNumber];
    
            System.out.println("请输入顶点的名称：");
            for (int i = 0; i < vertexNumber; i++) {
                String name = s.next();
                v[i] = new Vertex(name);
            }
    
            for (int i = 0; i < edgeNumber; i++) {
                System.out.print("输入第" + (i + 1) + "条有向边的端点A:");
                String startVertex = s.next();
                System.out.print("输入第" + (i + 1) + "条有向边的端点B:");
                String endVertex = s.next();
    
                // 找到起止点的vertex索引值
                int vBeginIndex = findvIndex(startVertex);
                int vEndIndex = findvIndex(endVertex);
    
                e[i] = new Edge(endVertex);// 由终点建立到该终点的边
                v[vEndIndex].indegree++;// 相应Vertex的入度+1
    
                e[i].nextEdge = v[vBeginIndex].first;// 将该边的下一条边连接到以startVertex的所有边
                v[vBeginIndex].first = e[i];// 将e作为v[startVertex]的第一条边
            }
        }
    
        public int getLength() {
            return v.length;
        }
    
        // 返回一个包含相邻节点的ArrayList
        public ArrayList<Vertex> getAdjacentVertex(Vertex ver) {
            int index;
            ArrayList al = new ArrayList();
    
            // 找到指向ver的相邻节点
            for (int j = 0; j < v.length; j++) {
                if (v[j].first != null)
                    for (Edge e = v[j].first; e != null; e = e.nextEdge)
                        if (e.to.equals(ver.from)) {
                            al.add(v[j]);
                        }
            }
            index = findvIndex(ver.from);
            // 找到以ver为起点指向的相邻节点
            for (Edge e = v[index].first; e != null; e = e.nextEdge) {
                al.add(v[findvIndex(e.to)]);
            }
    
            return al;
    
        }
    
        public int findvIndex(String s) {
            int vIndex = -1;
            for (int j = 0; j < v.length; j++) {
                if (v[j].from.equals(s))
                    vIndex = j;
            }
            return vIndex;
        }
    
    }

//主类：
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class BFS { 
    
        Graph g;
    
        public BFS() {
            g = new Graph();
            g.buildGraph();
        }
    
        public static void main(String[] args) {
            BFS s = new BFS();
            System.out.print("输入路径的起点：");
            Scanner input = new Scanner(System.in);
            String first = input.next();
            s.shortestPath(first);
        }
    
        public void shortestPath(String first) {
            LinkedList<Vertex> queue = new LinkedList<Vertex>();
            Vertex firstVertex = g.v[g.findvIndex(first)];
            firstVertex.setIsVisted(true);
            int counter = 0;
            firstVertex.setPathlength(counter);
            queue.add(firstVertex);
            System.out.println("最短路径为：");
            String path;
            while (!queue.isEmpty()) {
                Vertex v = queue.poll();
                // 得到队顶的path和Counter，用于下面for循环的赋值
                path = v.getFrom();
                counter = v.getPathlength();
                System.out.println(v.getFrom() + "的路径长度为 " + v.getPathlength());
                ArrayList<Vertex> al = g.getAdjacentVertex(v);
                for (Vertex vertex : al) {
                    if (!(vertex.getIsVisted()))// 没被访问过
                    {
                        vertex.setIsVisted(true);
                        vertex.setPathlength(counter + 1);
                        queue.add(vertex);
                    }
                }
    
            }
        }
    
    }

## **2.3 算法测试** ##

测试数据为下图：

![这里写图片描述][SouthEast 1]

**运行结果为：**  
![这里写图片描述][SouthEast 2]

[SouthEast]: /images/20220614/c1cae5738055431ba4a261740e061b4f.png
[SouthEast 1]: /images/20220614/c863748d22274752949e361f214c261c.png
[SouthEast 2]: /images/20220614/9c015391b8a64c148a602de679b6fcf0.png