Java利用Dijkstra算法求解拓扑关系最短路径

目录
  • 算法简介
  • 代码实现思路
  • 算法思想
  • 代码示例

算法简介

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学迪家迪杰斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点最短路劲算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

代码实现思路

1.先初始化源节点(起始点)到其他各个拓扑节点的最短距离,可以用map存放,key为节点,value为节点到源节点的距离。

比如数据库中存储的各个拓扑点的信息,我们需要先把数据库各地拓扑点之间的距离,加载出来,用map和矩阵(二维数组)方式。数据库拓扑信息存储表demo:

id source target dist
1 v1 v2 15.67

soure和target为相连的两个拓扑点,dist是相连接的两个拓扑点之间的距离。

2.初始化源节点到各个节点之间的距离时,源节点到自身节点的距离设为0,到不相连或者间接相连的节点距离设置为最大。

3.从源节点开始,不断循环迭代,各个节点到源节点的最短路线和距离,更新距离map里。当循环遍历到目标节点时,即可求出,源节点到目标节点的最短路线和距离。

更多说明,可以看代码注释。

算法思想

求最短路径步骤 [1]

算法步骤如下: [1]

G={V,E}

1. 初始时令 S={V0},T=V-S={其余顶点},T中顶点对应的距离值 [1]

若存在,d(V0,Vi)为弧上的权值 [1]

若不存在,d(V0,Vi)为∞ [2]

2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中 [1]

3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值 [1]

重复上述步骤2、3,直到S [1]  中包含所有顶点,即W=Vi为止 [1]

代码示例

import com.gis.spacedata.domain.entity.tunnel.TunnelTopologyRelEntity;
import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class PathUtil {

    /**
     * 方法描述: 求最短路径
     *
     */
    public static List<Long> dijkstra(List<TunnelTopologyRelEntity> topologies, long start, long end) {
        int size=topologies.size();
        Map<String, Double> distMap = new HashMap<>(size);
        //存放源节点到各个节点的距离key 目标节点,value 源节点到该节点的距离
        Map<Long, Double> dists = new HashMap<>(size);
        //key: 当前节点,value:从原点到达key的最短路径的前驱(上一个)节点
        Map<Long, Long> parent = new HashMap<>(size);
        //被标记最短距离的节点
        Set<Long> markNodes = new HashSet<>(size);
        //获取所有节点列表
        Set<Long> nodes = new HashSet<>(10);
        for (TunnelTopologyRelEntity e : topologies) {
            nodes.add(e.getSource());
            nodes.add(e.getTarget());
            distMap.put(e.getSource() + "-" + e.getTarget(), e.getCost());
        }
        //初始化各个节点到源节点的距离
        for (long node : nodes) {
            if (node == start) {
                dists.put(node, 0d);
            } else {
                dists.put(node, getCost(distMap, start, node));
            }
        }
        // 不断迭代
        while (true) {
            //距离源节点距离最近的节点(还未被标记为离源节点最近的点)
            long closestNode = -1;
            double min = Double.MAX_VALUE;
            for (Map.Entry<Long, Double> entry : dists.entrySet()) {
                if (entry.getValue() < min && !markNodes.contains(entry.getKey())) {
                    min = entry.getValue();
                    closestNode = entry.getKey();
                }
            }
            // 找不到可达的路径了或到达目标点
            if (closestNode == -1 || closestNode==end) {
                break;
            }
            markNodes.add(closestNode);
            for (long node : nodes) {
                double dist = getCost(distMap, closestNode, node);
                // 找到一个为扩展的子节点
                if (dist > 0 && !markNodes.contains(node)) {
                    double new_dist = dists.get(closestNode) + dist;
                    // 新距离小于原始距离,更新
                    if (new_dist < dists.get(node)) {
                        dists.put(node, new_dist);
                        parent.put(node, closestNode);
                    }
                }
            }
        }
        // 倒叙查找到路径
        if (dists.get(end) == Integer.MAX_VALUE) {
            log.info(start + "到" + end + "之间没有最短路径");
            return null;
        } else {
            List<Long> path = new ArrayList<>();
            long current = end;
            path.add(current);
            while (current != start) {
                current = parent.get(current);
                path.add(current);
            }
            //反转
            Collections.reverse(path);
            return path;
        }
    }

    /**
     * 方法描述: 获取相邻节点之间距离
     *
     */
    private static double getCost(Map<String, Double> distMap, long start, long end) {
        if (start == end) {
            return 0;
        }
        Double dist1 = distMap.get(start + "-" + end);
        if (dist1 != null) {
            return dist1;
        }
        Double dist2 = distMap.get(end + "-" + start);
        if (dist2 != null) {
            return dist2;
        }
        return Double.MAX_VALUE;
    }

}

实际业务代码中应用:

public List<Long> getPointShortWay(String startCode, String endCode) {
        TunnelTopologyCodeRelEntity startTopologyCodeRel = getTopologyCodeRel(startCode);
        TunnelTopologyCodeRelEntity endTopologyCodeRel = getTopologyCodeRel(endCode);
        if (Func.isNull(startTopologyCodeRel) || Func.isNull(endTopologyCodeRel)) {
            return Collections.emptyList();
        }
        List<TunnelTopologyRelEntity> list=list();
        return PathUtil.dijkstra(list,startTopologyCodeRel.getId(), endTopologyCodeRel.getId());
    }

到此这篇关于Java利用Dijkstra算法求解拓扑关系最短路径的文章就介绍到这了,更多相关Java Dijkstra算法求解最短路径内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java实现dijkstra最短路径寻路算法

    [引用]迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中顶点的路径是

  • Java利用Dijkstra和Floyd分别求取图的最短路径

    目录 1 最短路径的概述 2 杰斯特拉(Dijkstra)算法 2.1 原理 2.2 案例分析 3 弗洛伊德(Floyd)算法 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 本文详细介绍了图的最短路径的概念,然后介绍了求最短路径的两种算法:Dijkstra算法和Floyd算法的原理,最后提供了基于邻接矩阵和邻接表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最短路径的概述

  • java使用Dijkstra算法实现单源最短路径

    单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径.在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质. 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径.下面证明该性质的正确性. 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,

  • java实现Dijkstra最短路径算法

    任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式 用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下: 1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储

  • java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

  • Java实现Dijkstra输出最短路径的实例

    Java实现Dijkstra输出指定起点到终点的最短路径 前言: 最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径. 马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现. 而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出. package graph.dijsktra; import

  • Java利用Dijkstra算法求解拓扑关系最短路径

    目录 算法简介 代码实现思路 算法思想 代码示例 算法简介 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学迪家迪杰斯特拉于1959年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点最短路劲算法,解决的是有权图中最短路径问题.迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止. 代码实现思路 1.先初始化源节点(起始点)到其他各个拓扑节点的最短距离,可以用map存放,key为节点,value为节点到源节点的距

  • Java实现Dijkstra算法的示例代码

    目录 一 问题描述 二 实现 三 测试 一 问题描述 小明为位置1,求他到其他各顶点的距离. 二 实现 package graph.dijkstra; import java.util.Scanner; import java.util.Stack; public class Dijkstra { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int

  • Java利用蒙特卡洛方法求解圆周率π值

    目录 一.蒙特卡洛法介绍 二.利用蒙特卡洛方法计算圆周率π 三.实现代码 MTKLExp.java MonteCarloPiData.java Circle.java 一.蒙特卡洛法介绍 蒙特·卡罗方法(Monte Carlo method),也称统计模拟方法,是一种以概率统计理论为基础的数值计算方法,常用于特定条件下的概率计算问题.蒙特卡罗是摩纳哥的著名赌城,该法为表明其随机抽样的本质而命名. 算法思路简单也好理解:比如抛一枚硬币,假设我们开始不知道正面朝上的概率是多少,却有大量的时间来将硬币

  • java实现Dijkstra算法

    本文实例为大家分享了java实现Dijkstra算法的具体代码,供大家参考,具体内容如下 1 问题描述 何为Dijkstra算法? Dijkstra算法功能:给出加权连通图中一个顶点,称之为起点,找出起点到其它所有顶点之间的最短距离. Dijkstra算法思想:采用贪心法思想,进行n-1次查找(PS:n为加权连通图的顶点总个数,除去起点,则剩下n-1个顶点),第一次进行查找,找出距离起点最近的一个顶点,标记为已遍历:下一次进行查找时,从未被遍历中的顶点寻找距离起点最近的一个顶点, 标记为已遍历:

  • JS使用Dijkstra算法求解最短路径

    一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点

  • Java基于Dijkstra算法实现校园导游程序

    本文实例为大家分享了Dijkstra算法实现校园导游程序的具体代码,供大家参考,具体内容如下 应用设计性实验 1.问题描述 校网导游程序: 一个校园有若干景点,如正校门.人工湖.磁悬浮列车实验室.樱花大道.图书馆.体育场体育馆和礼堂等.实现一个为来访客 人提供信息在询服务的程序,如查询景点的详细信息,查询两个景点之间的一条最短路径. 2.实验要求 (1)设计你所在学校的校园平面图,所含景点不少于10个.(2)来访客人可以输人任一个景点的名称,查询景点的详细信息.(3)来访客人可以输人任何两个景点

  • java利用DFA算法实现敏感词过滤功能

    前言 敏感词过滤应该是不用给大家过多的解释吧?讲白了就是你在项目中输入某些字(比如输入xxoo相关的文字时)时要能检 测出来,很多项目中都会有一个敏感词管理模块,在敏感词管理模块中你可以加入敏感词,然后根据加入的敏感词去过滤输 入内容中的敏感词并进行相应的处理,要么提示,要么高亮显示,要么直接替换成其它的文字或者符号代替. 敏感词过滤的做法有很多,我简单描述我现在理解的几种: ①查询数据库当中的敏感词,循环每一个敏感词,然后去输入的文本中从头到尾搜索一遍,看是否存在此敏感词,有则做相 应的处理,

随机推荐

其他