08-最短路径算法

实现一个最短路径算法，并分析其时间复杂度和空间复杂度。

import java.util.*;

public class Graph {
    // 用Map来表示图的邻接表
    private Map<Integer, List<Node>> adjacencyList;

    // 构造函数，初始化邻接表
    public Graph(int vertices) {
        adjacencyList = new HashMap<>();
        for (int i = 1; i <= vertices; i++) {
            adjacencyList.put(i, new ArrayList<>());
        }
    }

    // 添加边
    public void addEdge(int source, int destination, int weight) {
        Node node = new Node(destination, weight);
        adjacencyList.get(source).add(node);

        node = new Node(source, weight);
        adjacencyList.get(destination).add(node);
    }

    // 获取起点到终点的最短路径
    public void dijkstra(int sourceVertex) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(adjacencyList.size(), Comparator.comparingInt(o -> o.cost));

        // 初始化距离数组和visited数组
        int[] distance = new int[adjacencyList.size()];
        boolean[] visited = new boolean[adjacencyList.size()];

        // 设置起点的距离为0，并将其加入优先队列
        distance[sourceVertex - 1] = 0;
        priorityQueue.add(new Node(sourceVertex, 0));

        // 处理优先队列中的节点，直到队列为空
        while (!priorityQueue.isEmpty()) {
            int currentVertex = priorityQueue.remove().vertex;

            if (visited[currentVertex - 1]) {
                continue;
            }

            visited[currentVertex - 1] = true;
            
            List<Node> adjacentNodes = adjacencyList.get(currentVertex);
            for (Node adjacentNode : adjacentNodes) {
                int adjacentVertex = adjacentNode.vertex;
                int edgeWeight = adjacentNode.cost;

                if (!visited[adjacentVertex - 1]) {
                    int newCost = distance[currentVertex - 1] + edgeWeight;
                    if (newCost < distance[adjacentVertex - 1]) {
                        distance[adjacentVertex - 1] = newCost;
                        priorityQueue.add(new Node(adjacentVertex, newCost));
                    }
                }
            }
        }

        // 打印起点到各个顶点的最短距离
        for (int i = 0; i < distance.length; ++i) {
            System.out.println("Distance from " + sourceVertex + " to " + (i + 1) + " is " + distance[i]);
        }
    }

    // 表示图中每个节点的类
    private static class Node {
        int vertex;
        int cost;

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

最短路径算法是用于找到图中两个节点之间的最短路径的一组算法。其中，Dijkstra's algorithm和Bellman-Ford algorithm是最常用的两种算法。其时间复杂度和空间复杂度如下：

• Dijkstra’s Algorithm

时间复杂度：O(ElogV)，其中E为边数，V为节点数。

空间复杂度：O(V)，其中V为节点数。

• Bellman-Ford Algorithm

时间复杂度：O(VE)，其中E为边数，V为节点数。

空间复杂度：O(V)，其中V为节点数。

需要注意的是，Dijkstra’s algorithm适用于有向无环图（DAG）或非负权重图，而Bellman-Ford algorithm则适用于带有负权重的图。

验证：

public static void main(String[] args) {
    Graph graph = new Graph(5);

    graph.addEdge(1, 2, 2);
    graph.addEdge(1, 4, 1);
    graph.addEdge(2, 3, 3);
    graph.addEdge(3, 4, 4);
    graph.addEdge(4, 5, 3);
    graph.addEdge(3, 5, 2);

    graph.dijkstra(1);
}