首页 > 其他分享 >安卓app 地铁最短路径查询 完成

安卓app 地铁最短路径查询 完成

时间:2024-03-29 22:44:44浏览次数:29  
标签:distance String get 安卓 最短 Map put adjacencyList app

 我通过三个函数 完成了这个功能

首先  创建哈希表 根据起始站名 终点站名

然后 根据哈希表 建立起 邻接表‘

最后 根据迪杰斯特拉算法 完成这个功能

 /**
     * function:起终查询
     */
    // 构建邻接表
    public static Map<String, Map<String, Integer>> buildAdjacencyList() {
        Connection connection = JDBCUtils.getConn();
        Map<String, Map<String, Integer>> adjacencyList = new HashMap<>();

        try {
            Statement statement = connection.createStatement();
            ResultSet resultSet = statement.executeQuery("SELECT Starting_Station, Terminus_Station FROM station");

            while (resultSet.next()) {

                String startingStation = resultSet.getString("Starting_Station");
                String terminusStation = resultSet.getString("Terminus_Station");

                addConnection(adjacencyList, startingStation, terminusStation);
                addConnection(adjacencyList, terminusStation, startingStation);
            }

            resultSet.close();
            statement.close();
            connection.close();
        } catch (SQLException e) {
            e.printStackTrace();
            // 适当处理 SQLException
        }

        return adjacencyList;
    }



    // 将连接添加到邻接表
    private static void addConnection(Map<String, Map<String, Integer>> adjacencyList, String source, String destination) {
        if (!adjacencyList.containsKey(source))
        {
            adjacencyList.put(source, new HashMap<>());
        }
        adjacencyList.get(source).put(destination, 1);
    }


    //根据 buildAdjacencyList()函数 求邻接表 最短路径
    public static List<String> shortest(User user) {
        String startingStation = user.getStarting_Station();
        String terminusStation = user.getTerminus_Station();

        Map<String, Map<String, Integer>> adjacencyList = buildAdjacencyList();
        Map<String, Integer> distance = new HashMap<>();
        Map<String, String> previous = new HashMap<>();
        PriorityQueue<String> queue = new PriorityQueue<>(Comparator.comparingInt(distance::get));

        for (String station : adjacencyList.keySet()) {
            distance.put(station, Integer.MAX_VALUE);
            previous.put(station, null);
        }

        distance.put(startingStation, 0);
        queue.add(startingStation);

        while (!queue.isEmpty()) {
            String currentStation = queue.poll();
            if (currentStation.equals(terminusStation)) {
                break; // Found shortest path to terminus station
            }

            Map<String, Integer> neighbors = adjacencyList.get(currentStation);
            if (neighbors != null) {
                for (String neighbor : neighbors.keySet()) {
                    int alt = distance.get(currentStation) + neighbors.get(neighbor);
                    if (alt < distance.get(neighbor)) {
                        distance.put(neighbor, alt);
                        previous.put(neighbor, currentStation);
                        queue.add(neighbor);
                    }
                }
            }
        }

        // Reconstruct shortest path
        List<String> shortestPath = new ArrayList<>();
        String current = terminusStation;
        while (previous.get(current) != null) {
            shortestPath.add(current);
            current = previous.get(current);
        }
        shortestPath.add(startingStation);
        Collections.reverse(shortestPath);

        System.out.println(shortestPath);

        return shortestPath;

    }

 

标签:distance,String,get,安卓,最短,Map,put,adjacencyList,app
From: https://www.cnblogs.com/youxiandechilun/p/18104763

相关文章

  • qt窗口的应用与pyinstaller打包APP操作
    3月29日qt打包APP操作1先在windowsshell中下载打包软件Pylnstallerpipinstallpyinstaller2先进入py项目所在的位置,再执行以下代码(我用的qt版本是PySide6可以根据自己的情况修改)pyinstallers02.py--noconsole--hidden-importPySide6.QtXml3因为打包的时......
  • AcWing—最短Hamilton路径
    91.最短Hamilton路径-AcWing题库所需知识:二进制状态压缩,动态规划假设现在有六个点:j/i012345002451312065312460832355805441335035312430起点为0终点为5,假设现在走到终点前一点,不妨设该点为4,即现在要确定从0到4,最少要走多远,起点为1终点为4,现有六条路可以选择:first:0–......
  • Android 标题栏Toolbar,安卓高级开发面试题
    super.onCreate(savedInstanceState);setContentView(R.layout.activity_main);init();}privatevoidinit(){toolbar=(Toolbar)findViewById(R.id.toolbar);//使用Toolbar替换ActionBarsetSupportActionBar(toolbar);}ToolBar的Action操作ToolBar的一大亮......
  • A Systematic Survey of Prompt Engineering in Large Language Models: Techniques a
    本文是LLM系列文章,针对《ASystematicSurveyofPromptEngineeringinLargeLanguageModels:TechniquesandApplications》的翻译。大型语言模型中提示工程的系统综述:技术与应用摘要1引言2提示工程3结论摘要提示工程已经成为扩展大型语言模型(LLM)和视......
  • P1354 房间最短路问题
    原题链接题解1.最短路径一定可以表示成经过若干端点的线段,所以我们把端点单独提出来,这样就变成了计算几何形式的最短路2.如果两个端点能相连,代表他们之间没有墙阻挡code#include<bits/stdc++.h>usingnamespacestd;intn;struct{doublex,a1,b1,a2,b2;}wall[30];......
  • 如何高效的开展app的性能测试?
    APP性能测试是什么从网上查了一下,貌似也没什么特别的定义,我这边根据自己的经验给出一个自己的定义,如有巧合纯属雷同。客户端性能测试就是,从业务和用户的角度出发,设计合理且有效的性能测试场景,制定各性能场景下的客户端性能指标(内存、CPU、卡顿数、帧率、电量、加载时长等),并制......
  • WebApplicationBuilder
    WebApplicationBuilder类(Microsoft.AspNetCore.Builder)|MicrosoftLearnWebApplicationBuilder属性Configuration要撰写的应用程序的配置提供程序的集合。这对于添加新的配置源和提供程序很有用。Environment提供有关应用程序正在运行的Web托管环境的信息......
  • 使用Andorid Studio解决app内存泄漏问题方法与实践
    某项目的app运行一段时间(切换页面、触发交互事件等)后就开始严重卡顿,使用top查看内存的使用情况,发现每次操作过后内存都有小幅增长,且永远不下降,存在内存泄露问题。目录1AndoridStudio内存泄露检测工具使用方法2内存泄露实例分析2.1页面切换后未主动释放​编辑2.2回调......
  • MIUI安卓录音机文件位置
    旧版:在“/storage/sdcard0/MIUI/sound_recorder/”里的相应文件夹里。新版:在“/手机存储/Android/data/com.android.soundrecorder/files”里的相应文件夹里。猴米自身的文件管理器无法打开,得使用安卓原生自带的文件管理器(可以通过猴米文件管理器调用)为遵循安卓规范与保护录......
  • Bootloader/IAP零基础入门(1.1) —— 设计一个Bootloader引导进入APP的程序,包含中断向量
    前言(1)如果有嵌入式企业需要招聘湖南区域日常实习生,任何区域的暑假Linux驱动/单片机/RTOS的实习岗位,可C站直接私聊,或者邮件:[email protected],此消息至2025年1月1日前均有效(2)在上一章节中,我们详细介绍了如何让Bootloader引导进入APP程序。但是上一章节的工程是无法使用......