即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

JAVA广度优先实现最短路径相关疑难问题

编程语言 yuanlaijike 80℃ 0评论
本文目录
[隐藏]

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

1.一、点到点

1.1.1.1 问题描述

这里采用迷宫问题来举例。求从起点到终点的最短路径,采用广度优先的顺序,首先将与源点邻接的顶点的路径求出,然后再依次求解图中其他顶点的最短路径。


由于顶点的最短路径的求解顺序 是一个广度优先的顺序,因此需要一个辅助队列。具体步骤如下:


①从起点开始,先将其加入队列,设置距离为0;


②从队列首端取出位置,将从这个位置能够到达的位置加入队列,并且让这些位置的距离为上一个位置的距离加上1;


③循环2直到将终点添加到队列中,这说明我们已经找到了路径;


在这个过程中,每次处理的位置所对应的距离是严格递增的,因此一旦找到终点,当时的距离就是最短距离。


由此可见,迷宫问题是一个无向无权图。

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 q = new LinkedList();
        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.1.3 算法测试

测试数据为10*10矩阵;


矩阵为:


1111111111


1m01000101


1001000101


1000011001


1011100001


1000100001


1010001001


1011101101


11000000e1


1111111111

运行结果为:


这里写图片描述

2.二、源点到其他点

2.1.2.1 问题描述

源点的最短路径距离为0,从源点开始,采用广度优先的顺序,首先将与源点邻接的顶点的路径求出,然后再依次求解图中其他顶点的最短路径。


由于顶点的最短路径的求解顺序、是一个广度优先的顺序,因此需要一个辅助队列。初始时,将源点的最短路径距离设置为0,将源点入队列。


然后,在一个while循环中,从队列中弹出顶点,遍历该顶点的邻接点,若该邻接点的距离未被更新过(表示该邻接点未被访问过),更新邻接点的最短路径距离为该顶点的距离加上1,并将所有的邻接点入队列。


这里采用的图为有向无权图。

2.2.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 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 queue = new LinkedList();
        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 al = g.getAdjacentVertex(v);
            for (Vertex vertex : al) {
                if (!(vertex.getIsVisted()))// 没被访问过
                {
                    vertex.setIsVisted(true);
                    vertex.setPathlength(counter + 1);
                    queue.add(vertex);
                }
            }

        }
    }

}

2.3.2.3 算法测试

测试数据为下图:

这里写图片描述

运行结果为:


这里写图片描述

转载请注明:CodingBlog » JAVA广度优先实现最短路径相关疑难问题

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情