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);
    }
}

这个示例中，我们创建了一个包含6个顶点的图，并添加了一些边。然后，我们从顶点0开始运行Dijkstra算法，计算并打印出从顶点0到所有其他顶点的最短路径距离。