首页 > 编程语言 >Java中的图算法:如何实现高效的最短路径计算

Java中的图算法:如何实现高效的最短路径计算

时间:2024-08-17 13:23:38浏览次数:13  
标签:dist int graph 路径 算法 Java 节点

Java中的图算法:如何实现高效的最短路径计算

大家好,我是微赚淘客系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿! 作为开头。

最短路径算法是图论中的一个核心问题,广泛应用于网络路由、地图导航等领域。在 Java 中实现高效的最短路径计算通常涉及到 Dijkstra 算法和 Floyd-Warshall 算法等。这些算法各有特点,适用于不同类型的图和需求。本文将详细介绍这些算法及其在 Java 中的实现。

1. Dijkstra 算法

Dijkstra 算法是解决单源最短路径问题的经典算法,适用于带权图,且边权非负。它的核心思想是逐步扩展最短路径,直到找到目标节点的最短路径。

算法步骤:

  1. 初始化

    • 将源节点的距离设为0,其余节点的距离设为无穷大。
    • 创建一个优先队列(最小堆)来选择当前最小的距离节点。
  2. 扩展节点

    • 从队列中取出距离最小的节点。
    • 更新其相邻节点的距离。
    • 将更新后的节点重新加入队列。
  3. 结束

    • 当队列为空时,算法结束,所有节点的最短路径都已找到。

以下是 Dijkstra 算法的 Java 实现:

package cn.juwatech.graph;

import java.util.Arrays;
import java.util.PriorityQueue;

public class DijkstraAlgorithm {

    // 节点类
    static class Node implements Comparable<Node> {
        int vertex;
        int distance;

        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    // Dijkstra 算法
    public static int[] dijkstra(int[][] graph, int source) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.add(new Node(v, newDist));
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 7, 9, 0, 0, 14},
            {7, 0, 10, 15, 0, 0},
            {9, 10, 0, 11, 0, 2},
            {0, 15, 11, 0, 6, 0},
            {0, 0, 0, 6, 0, 9},
            {14, 0, 2, 0, 9, 0}
        };

        int source = 0;
        int[] distances = dijkstra(graph, source);

        System.out.println("从源节点 " + source + " 到各个节点的最短距离:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("到节点 " + i + " 的最短距离为 " + distances[i]);
        }
    }
}
代码说明
  1. Node 类:表示图中的节点及其到源节点的距离,重写 compareTo 方法以支持优先队列的最小堆功能。
  2. dijkstra 方法
    • 初始化距离数组和优先队列。
    • 从源节点开始,扩展距离最短的节点。
    • 更新相邻节点的最短距离,并将更新后的节点加入队列。
  3. main 方法
    • 示例图以邻接矩阵表示,调用 dijkstra 方法计算最短路径。
    • 输出从源节点到各个节点的最短距离。

2. Floyd-Warshall 算法

Floyd-Warshall 算法是解决多源最短路径问题的经典算法,适用于任何类型的图(包括负权边)。它的核心思想是逐步更新每对节点之间的最短路径。

算法步骤:

  1. 初始化

    • 使用一个二维数组表示图的边权。
    • 对于每对节点 (i, j),初始化距离为边权,若没有直接边,则设为无穷大。
  2. 更新路径

    • 对于每个中间节点 k,检查通过 k 是否能找到更短的路径。
    • 更新路径长度数组。
  3. 结束

    • 遍历完成后,所有节点对之间的最短路径已计算完毕。

以下是 Floyd-Warshall 算法的 Java 实现:

package cn.juwatech.graph;

import java.util.Arrays;

public class FloydWarshallAlgorithm {

    // Floyd-Warshall 算法
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else if (graph[i][j] != 0) {
                    dist[i][j] = graph[i][j];
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, 0, 0, 0, 0},
            {3, 0, 1, 0, 0, 0},
            {0, 1, 0, 7, 0, 2},
            {0, 0, 7, 0, 2, 0},
            {0, 0, 0, 2, 0, 3},
            {0, 0, 2, 0, 3, 0}
        };

        int[][] distances = floydWarshall(graph);

        System.out.println("任意两点之间的最短距离:");
        for (int i = 0; i < distances.length; i++) {
            for (int j = 0; j < distances[i].length; j++) {
                if (distances[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(distances[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}
代码说明
  1. floydWarshall 方法
    • 初始化距离矩阵,若存在直接边则设置为边权,否则为无穷大。
    • 通过逐步检查中间节点,更新每对节点之间的最短路径。
  2. main 方法
    • 示例图以邻接矩阵表示,调用 floydWarshall 方法计算所有节点对之间的最短路径。
    • 输出每对节点之间的最短路径。

3. 性能考虑

  • 时间复杂度

    • Dijkstra 算法:使用优先队列时时间复杂度为 (O((V + E) \log V)),其中 (V) 是节点数,(E) 是边数。
    • Floyd-Warshall 算法:时间复杂度为 (O(V^3))。
  • 空间复杂度

    • Dijkstra 算法:空间复杂度为 (O(V))。
    • Floyd-Warshall 算法:空间复杂度为 (O(V^2))。
  • 适用场景

    • Dijkstra 算法适用于边权非负的图,且适合单源最短路径问题。
    • Floyd-Warshall 算法适用于所有边权的图,且适合多源最短路径问题。

本文著作权归聚娃科技微赚淘客系统开发者团队,转载请注明出处!

标签:dist,int,graph,路径,算法,Java,节点
From: https://blog.csdn.net/weixin_44409190/article/details/141268556

相关文章

  • 点亮职场之路,从优化简历开始 —— 专业Java简历优化服务,助您脱颖而出
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java技术的浩瀚星海中,每一位求职者都是独特的星辰,但如何让自己在众多候选人中熠熠生辉,成为企业争抢的“宝藏”?答案,就藏在......
  • Java简历优化专家 —— 打造您的职业名片,引领梦想职位之旅
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java编程的征途上,每一步都至关重要。而一份精心优化的简历,正是您迈向理想职位的第一步。我们深知,每一位Java求职者都渴望......
  • 面试题:在Java中,JVM(Java虚拟机)的内存模型是如何设计的?请详细解释堆(Heap)、栈(Stack)、方法
    面试题:在Java中,JVM(Java虚拟机)的内存模型是如何设计的?请详细解释堆(Heap)、栈(Stack)、方法区(MethodArea)以及程序计数器(ProgramCounterRegister)的作用和它们之间的关系。更多答案在这里,手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项......
  • 面试题:在Java中,线程之间的通信主要通过哪几种方式实现?并简述其中一种方式的基本工作原
    面试题:在Java中,线程之间的通信主要通过哪几种方式实现?并简述其中一种方式的基本工作原理。请注意,除了直接回答此问题外,我们还为您准备了更多深入的学习资源和面试技巧。想要了解更多关于Java线程通信、优化简历、模拟面试、企业项目源码、大厂高并发面试题、项目场景题、算法......
  • 面试题:在Java中,多线程编程是常见的并发处理方式。请简述Java中实现多线程的几种主要方
    面试题:在Java中,多线程编程是常见的并发处理方式。请简述Java中实现多线程的几种主要方式,并解释每种方式的基本思想。更多关于多线程编程的深入解析、面试技巧、以及实战项目源码,手机浏览器即可访问面霸宝典【全拼音】.com,这里不仅可以优化你的简历,还能进行模拟面试,获取最新最......
  • 【Java求职者的福音:专业简历优化服务,助力梦想启航】
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java技术的浩瀚星海中,您是那颗璀璨的新星,正蓄势待发,准备在职场上绽放光芒。但在这个充满机遇与挑战的时代,如何让您的简历......
  • 面试题:在Java中,volatile 关键字的作用是什么?它与 synchronized 关键字在实现线程同步
    面试题:在Java中,volatile 关键字的作用是什么?它与 synchronized 关键字在实现线程同步方面有何不同?请深入探讨其背后的原理和应用场景。更多答案在这里,手机或电脑浏览器就可以打开, 面霸宝典【全 拼音】.com 这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并......
  • 【Java求职者的职场加速器:专业简历优化服务,助您脱颖而出】
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java编程的征途上,您已积累了丰富的技术经验和项目成果,但面对激烈的职场竞争,如何让自己的简历在众多求职者中脱颖而出,成为......
  • 定制辉煌,领跑职场 —— Java简历优化服务,助您跨越求职高峰
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java技术的浩瀚星海中,每一颗闪耀的星星都代表着一位优秀开发者的才华与梦想。但如何让自己的光芒在求职路上更加耀眼?我们......
  • 学习Java第七周
    本周学习一、1.修饰符classSubClassextendsSuperClass{//类定义部分}表明继承了SuperClass类。注:子类只能从被扩展的父类获得成员变量、方法和内部类(包括内部接口、枚举),不能获得构造器和初始化块。2.Java类只能有一个直接父类,实际上,Java类可以有无限多个间接父类。3......