Java语言实现最短路径算法（Shortest Path）-阿里云开发者社区

Java语言实现最短路径算法（Shortest Path）

2024-07-29 40

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java语言实现最短路径算法（Shortest Path）

Java语言实现最短路径算法（Shortest Path）在Java中实现最短路径算法，可以选择经典的Dijkstra算法。Dijkstra算法是一种用于计算加权图中单源最短路径的贪心算法。下面是一个简单的Dijkstra算法实现示例：

import java.util.*;
public class Dijkstra {
    static class Edge {
        int target;
        int weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    static class Graph {
        int vertices;
        LinkedList<Edge>[] adjacencyList;
        Graph(int vertices) {
            this.vertices = vertices;
            adjacencyList = new LinkedList[vertices];
            for (int i = 0; i < vertices; i++) {
                adjacencyList[i] = new LinkedList<>();
            }
        }
        void addEdge(int source, int target, int weight) {
            adjacencyList[source].add(new Edge(target, weight));
            adjacencyList[target].add(new Edge(source, weight));  // 如果是有向图，则去掉这一行
        }
        void dijkstra(int startVertex) {
            boolean[] visited = new boolean[vertices];
            int[] distances = new int[vertices];
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[startVertex] = 0;
            PriorityQueue<Edge> pq = new PriorityQueue<>(vertices, Comparator.comparingInt(e -> e.weight));
            pq.add(new Edge(startVertex, 0));
            while (!pq.isEmpty()) {
                Edge edge = pq.poll();
                int vertex = edge.target;
                if (visited[vertex]) continue;
                visited[vertex] = true;
                LinkedList<Edge> edges = adjacencyList[vertex];
                for (Edge e : edges) {
                    int target = e.target;
                    int weight = e.weight;
                    if (!visited[target] && distances[vertex] + weight < distances[target]) {
                        distances[target] = distances[vertex] + weight;
                        pq.add(new Edge(target, distances[target]));
                    }
                }
            }
            printShortestPaths(startVertex, distances);
        }
        void printShortestPaths(int startVertex, int[] distances) {
            System.out.println("Vertex\tDistance from Source " + startVertex);
            for (int i = 0; i < vertices; i++) {
                System.out.println(i + "\t\t" + distances[i]);
            }
        }
    }
    public static void main(String[] args) {
        int vertices = 6;
        Graph graph = new Graph(vertices);
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 6);
        graph.dijkstra(0);
    }
}