专栏首页JavaEE迪杰斯特拉算法(最短路径问题)

迪杰斯特拉算法(最短路径问题)

1. 应用场景:

假如有七个村庄(ABCDEFG),有个人从G点出发,到其他六个村庄的最短路径分别是多少?到A、B、F、E只有一条路,没得选,但是到C有两条路,可以是2 + 7,也可以是8 + 4,到D点可以是3 + 9,也可以是6 + 4。图上标明了距离我们当然一看就知道怎么选,那么如何能让程序选择最短的路径呢?

最短路径问题

迪杰斯特拉算法就是求最短路径的经典算法。它的主要思想就是以起始点向外层层扩展,用广度优先的思想,直到扩展到终点为止。

2. 算法步骤:

以上面的例子,从G开始处理,来讲解这个过程:

  • 首先我们会用一个数组或者集合来保存这7个顶点,如下:
String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
  • 其次,会有一个邻接矩阵来表示各个顶点之间的距离,如下(N表示联不通,可以用一个很大的数表示):
  A  B  C  D  E  F  G
A{N, 5, 7 ,N, N, N, 2}
B{5, N, N ,9, N, N, 3}
C{7, N, N ,N, 8, N, N}
D{N, 9, N ,N, N, 4, N}
E{N, N, 8 ,N, N, 5, 4}
F{N, N, N ,4, 5, N, 6}
G{2, 3, N ,N, 4, 6, N}
  • 接着创建一个数组already_arr,长度为顶点的个数。数组里面,0表示未访问过该顶点,1表示访问过该顶点。初始的时候其他都是0,G顶点的是1。
int[] already_arr = {0, 0, 0, 0, 0, 0, 1};
  • 再创建一个数组dis,长度也是顶点的个数。该数组记录的是当前顶点到其他顶点的距离,初始的时候是一个较大的数,到自己的距离就是0。
int[] dis = {N, N, N, N, N, N, 0};
  • 还要创建一个数组pre_visited,长度也是顶点的个数。数组表示顶点的到前驱顶点的距离,初始时候都是0。
int[] pre_visited = {0, 0, 0, 0, 0, 0, 0};
  • 处理了顶点G,即邻接矩阵的最后一行,可以发现,G到A的距离是2,小于9999,到B的距离是3,也小于9999……所以更新dis数组,如下:
int[] dis = {2, 3, N, N, 4, 6, 0};
  • 从邻接矩阵的最后一行可以看出,G和A、B、E、F是直接连通的,也就说明,ABEF这四个点的前驱顶点都是G,所以pre_visited数组变成了:
int[] pre_visited = {6, 6, 0, 0, 6, 6, 0};
  • 上面就是第一次的处理过程,然后按照广度优先的方式,每访问一个顶点,就按照上面的方式去修改这3个数组。最后的G顶点到每个顶点的最短距离就记录中dis数组中。

3. 代码实现:

  • 首先得把图创建出来:
class Graph{
    String[] vertexs; // 存放顶点
    int[][] edges; // 邻接矩阵,存放边
    
    public Graph(String[] vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
    }
}
  • 然后,创建一个类,类里面有个三个属性,就是上面说的那三个数组,以及一些必要的方法:
class VisitedVertex{
    
    private static final int N = 999;
    
    public int[] already_arr;
    public int[] pre_visited;
    public int[] dis;
    
    /**
     * 构造器
     * @param length 顶点的个数
     * @param index 出发点的索引
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        // 初始化dis数组
        Arrays.fill(dis, N);
        dis[index] = 0;
    }
    
    /**
     * 判断index对应的顶点是否被访问过
     * @param index
     * @return
     */
    public boolean isVisited(int index) {
        return already_arr[index] == 1;
    }
    
    /**
     * 更新dis数组,索引为index的值更新为len
     * @param index
     * @param len
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }
    
    /**
     * 更新前驱顶点
     * @param index
     * @param val
     */
    public void updatePre(int index, int val) {
        pre_visited[index] = val;
    }
    
/**
     * 将index设置为已访问
     * @param index
     */
    public void updateAlreadyArr(int index) {
        already_arr[index] = 1;
    }

    /**
     * 返回出发顶点到index这个顶点的距离
     * @param index
     * @return
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 返回要处理的下一个顶点
     * @return
     */
    public int nextVertexs() {
        int index = 0;
        int min = N;
        for (int i=0; i< already_arr.length; i++) {
            if (!isVisited(i) && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        updateAlreadyArr(index);
        return index;
    }
    
    public void printArr() {
        System.out.println(Arrays.toString(this.dis) + "   dis");
        System.out.println(Arrays.toString(this.pre_visited) + "   pre_visited");
        System.out.println(Arrays.toString(this.already_arr) + "   already_arr");
    }
}
  • 那么接下来就可以在Graph类中新增一个方法,来实现迪杰斯特拉算法了,如下:
    /**
     * 迪杰斯特拉算法实现
     * @param index 出发顶点的下标
     */
    public void dsj(int index) {
        VisitedVertex visitedVertex = new VisitedVertex(this.vertexs.length, index);
        updateArrs(index, visitedVertex);
        // 下一个要处理的顶点
        for (int i=1; i<vertexs.length; i++) {
            index = visitedVertex.nextVertexs();
            updateArrs(index, visitedVertex);
        }
        visitedVertex.printArr();
    }
    
    /**
     * 拿到邻接矩阵的第index行,根据这一行对三个数组进行更新
     * @param index
     * @param visitedVertex
     */
    private void updateArrs(int index, VisitedVertex visitedVertex) {
        int[] tempArr = this.edges[index];
        // distance表示出发顶点到索引为index的这个顶点的距离
        int distance = 0;
        for (int i=0; i< tempArr.length; i++) {
            // 先前的距离 + 本次遍历得到的距离
            distance = visitedVertex.getDis(index) + tempArr[i];
            if (distance < visitedVertex.getDis(i) && !visitedVertex.isVisited(i)) {
                visitedVertex.updateDis(i, distance);
                visitedVertex.updatePre(i, index);
                visitedVertex.updateAlreadyArr(index);
            }
        }
    }

测试方法:

public class DijkstraDemo {
    
    public static final int N = 999;

    public static void main(String[] args) {
        String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
        int[][] edges = {
            {N, 5, 7 ,N, N, N, 2},
            {5, N, N ,9, N, N, 3},
            {7, N, N ,N, 8, N, N},
            {N, 9, N ,N, N, 4, N},
            {N, N, 8 ,N, N, 5, 4},
            {N, N, N ,4, 5, N, 6},
            {2, 3, N ,N, 4, 6, N}
        };
        Graph graph = new Graph(vertexs, edges);
        graph.dsj(6);
    }
}

运行后得到结果如下:

运行结果

dis数组就是我们想要的结果,即对应的顶点G到各个点的最短距离。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最短路径问题--迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科学家狄克斯特拉于1959年提出,用来求从起始点到其他所有点...

    用户6021899
  • 最短路径-----迪杰特斯拉算法

    大忽悠爱学习
  • 算法:最短路径之迪杰斯特拉(Dijkstra)算法

    对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Di...

    s1mba
  • 最短路径算法(上)——迪杰斯特拉(Dijikstra)算法

    对于迪杰斯特拉算法的分支界限法解法请移步:利用分支界限法求解Dijikstra算法

    AI那点小事
  • C++迪杰斯特拉最短路径算法实现

    input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

    kalifa_lau
  • 单源最短路径之迪杰斯特拉算法

    迪杰斯特拉(Dijkstra)算法解决最短路径问题,其创造者:艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra)。

    每天学Java
  • 最短路径—弄懂Dijkstra(迪杰斯特拉)算法

    对于 dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解 bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法...

    bigsai
  • 迪杰斯特拉(Dijkstra)算法求图中最短路径

    迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

    Steve Wang
  • 数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩...

    越陌度阡

扫码关注云+社区

领取腾讯云代金券