java算法公交车线路以最低票价从一个场所到另一个场所且有带权有向图的代码

以下是Java实现的Dijkstra算法，用于在带权有向图中寻找从一个场所到另一个场所的最短路径：

import java.util.*;

public class Dijkstra {
    
    // 顶点数量
    private int V;
    
    // 邻接表
    private List<List<Edge>> adj;
    
    // 构造函数
    public Dijkstra(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; ++i) {
            adj.add(new ArrayList<>());
        }
    }
    
    // 添加边
    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
    }
    
    // Dijkstra算法
    public int dijkstra(int src, int dest) {
        // 初始化距离数组
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // 创建优先队列
        PriorityQueue<Node> pq = new PriorityQueue<>(V, Comparator.comparingInt(o -> o.dist));
        pq.add(new Node(src, 0));
        
        // 运行Dijkstra算法
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.u;
            int d = node.dist;
            
            // 如果当前顶点的距离已经大于等于目标顶点，则可以提前结束算法
            if (u == dest) {
                return dist[dest];
            }
            
            // 如果当前顶点的距离已经大于等于最短距离，则可以跳过该顶点
            if (d > dist[u]) {
                continue;
            }
            
            // 遍历所有相邻的顶点
            for (Edge e : adj.get(u)) {
                int v = e.v;
                int w = e.w;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        
        // 如果没有找到目标顶点，则返回-1
        return -1;
    }
    
    // 边类
    class Edge {
        int v;
        int w;
        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    
    // 节点类
    class Node {
        int u;
        int dist;
        Node(int u, int dist) {
            this.u = u;
            this.dist = dist;
        }
    }
}

使用示例：

public static void main(String[] args) {
    Dijkstra dijkstra = new Dijkstra(4);
    dijkstra.addEdge(0, 1, 10);
    dijkstra.addEdge(0, 2, 5);
    dijkstra.addEdge(1, 2, 2);
    dijkstra.addEdge(1, 3, 1);
    dijkstra.addEdge(2, 1, 3);
    dijkstra.addEdge(2, 3, 9);
    int shortestPath = dijkstra.dijkstra(0, 3);
    System.out.println("Shortest path from 0 to 3 is " + shortestPath);
}

输出结果：

Shortest path from 0 to 3 is 6