import java.util.*;
class Graph {   // 圖
    private List<Vertex> vertices;  // 頂點(diǎn)集
    public Graph() {
        vertices = new ArrayList<Vertex>();
    }
    public void addVertex(Vertex v) {   // 添加頂點(diǎn)
        vertices.add(v);
    }   // 添加頂點(diǎn)
    public List<Vertex> getVertices() { // 返回頂點(diǎn)
        return vertices;
    }   // 獲取頂點(diǎn)集
}
class Vertex {  // 點(diǎn)
    private int id; // 點(diǎn) id
    private List<Edge> edges;   // 連接到該頂點(diǎn)的邊
    private int distance;   // 從源頂點(diǎn)到該頂點(diǎn)的最短距離，MAX_VALUE init
    private boolean visited;    // 在圖的遍歷過(guò)程中是否訪問(wèn)過(guò)該頂點(diǎn)，false init
    public Vertex(int id) {
        this.id = id;
        edges = new ArrayList<Edge>();
        distance = Integer.MAX_VALUE;
        visited = false;
    }
    public int getId() {    // 獲取 id
        return id;
    }
    public void addEdge(Edge e) {   // 將連接到該頂點(diǎn)邊添加到列表中
        edges.add(e);
    }   // 添加圖到邊
    public List<Edge> getEdges() {  // 獲取連接到該頂點(diǎn)的邊集
        return edges;
    }   // 獲取圖中邊
    public int getDistance() {  // 獲取從源頂點(diǎn)到該頂點(diǎn)的最短距離
        return distance;
    }   // 獲取源頂點(diǎn)到該頂點(diǎn)的最短距離
    public void setDistance(int distance) { //設(shè)置最短距離
        this.distance = distance;
    }   // 設(shè)置源頂點(diǎn)到該頂點(diǎn)的最短距離
    public boolean isVisited() {    // 獲取在圖的遍歷過(guò)程中是否訪問(wèn)過(guò)該點(diǎn)
        return visited;
    }   // 獲取圖遍歷過(guò)程中是否訪問(wèn)過(guò)該點(diǎn)
    public void setVisited(boolean visited) {   // 設(shè)置在圖的遍歷過(guò)程中是否訪問(wèn)過(guò)該點(diǎn)
        this.visited = visited;
    }   // 設(shè)置圖遍歷過(guò)程中是否訪問(wèn)過(guò)該點(diǎn)
}
class Edge {    // 邊
    private Vertex source;  // 源頂點(diǎn)
    private Vertex destination; // 目標(biāo)頂點(diǎn)
    private int weight; // 邊的權(quán)重
    public Edge(Vertex source, Vertex destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
    public Vertex getSource() { // 返回源頂點(diǎn)
        return source;
    }   // 獲取源點(diǎn)
    public Vertex getDestination() {    // 返回目標(biāo)頂點(diǎn)
        return destination;
    }   // 獲取目標(biāo)頂點(diǎn)
    public int getWeight() {    // 獲取邊的權(quán)重
        return weight;
    }   // 獲取邊的權(quán)重
}
// SPFA 算法
public class SPFA { 
    public static void spfa(Graph graph, Vertex source) {
        // 初始化
        Queue<Vertex> queue = new LinkedList<Vertex>(); // 初始化一個(gè)頂點(diǎn)隊(duì)列，使用該隊(duì)列來(lái)跟中需要處理的頂點(diǎn) 
        for (Vertex v : graph.getVertices()) {  // 初始化最短距離和是否訪問(wèn)過(guò)該點(diǎn)
            v.setDistance(Integer.MAX_VALUE);
            v.setVisited(false);
        }
        source.setDistance(0); // 將源頂點(diǎn)到自身的最短距離設(shè)為0
        queue.add(source);  // 將源頂點(diǎn)添加到隊(duì)列中
        // 迭代
        int count = 0;  // 用于檢測(cè)圖中的負(fù)環(huán)，count超過(guò)圖中頂點(diǎn)的總數(shù)，拋出異常
        // 查找從一個(gè)源頂點(diǎn)到圖中所有其它頂點(diǎn)的最短路徑
        while (!queue.isEmpty()) {  
            Vertex u = queue.poll();    // 存儲(chǔ)SPFA算法正在處理的頂點(diǎn)，poll 方法將下一個(gè)頂點(diǎn)從隊(duì)列中取出
            u.setVisited(false);    // 標(biāo)記該頂點(diǎn)為未訪問(wèn)，以便在算法中再次對(duì)其處理
            // 查找部分，循環(huán)遍歷當(dāng)前頂點(diǎn) u 的所有邊
            for (Edge e : u.getEdges()) {   
                Vertex v = e.getDestination();  // 返回邊 e 的目標(biāo)頂點(diǎn)給 v
                int distance = u.getDistance() + e.getWeight(); // 計(jì)算源頂點(diǎn)到目標(biāo)頂點(diǎn)的距離
                if (distance < v.getDistance()) {
                    v.setDistance(distance);    // 更新最短距離
                    if (!v.isVisited()) {   // 如果該頂點(diǎn)未被訪問(wèn)過(guò)
                        queue.add(v);   // 將該頂點(diǎn)添加到隊(duì)列中
                        v.setVisited(true); // 標(biāo)記該頂點(diǎn)已被訪問(wèn)
                        count++;    // 負(fù)環(huán) + 1
                        if (count > graph.getVertices().size()) {   // 檢查 SPFA 算法處理的頂點(diǎn)數(shù)是否大于圖中頂點(diǎn)總數(shù)
                            throw new RuntimeException("Negative cycle detected");
                        }
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        // 構(gòu)造圖
        Graph graph = new Graph();
        // 構(gòu)造頂點(diǎn)
        Vertex s = new Vertex(0);
        Vertex a = new Vertex(1);
        Vertex b = new Vertex(2);
        Vertex c = new Vertex(3);
        Vertex d = new Vertex(4);
        // 點(diǎn)加邊
        s.addEdge(new Edge(s, a, 2));
        s.addEdge(new Edge(s, c, 1));
        a.addEdge(new Edge(a, b, 3));
        b.addEdge(new Edge(b, d, 2));
        c.addEdge(new Edge(c, d, 1));
        // 邊加點(diǎn)
        graph.addVertex(s);
        graph.addVertex(a);
        graph.addVertex(b);
        graph.addVertex(c);
        graph.addVertex(d);
        // 調(diào)用SPFA算法求解最短路徑
        spfa(graph, s);
        // 輸出結(jié)果
        for (Vertex v :graph.getVertices()) {
            System.out.println("Shortest distance from source to vertex " + v.getId() + " is " + v.getDistance()); 
        } 
    } 
}