Dijkstra（迪傑斯特拉算法）的Java完整版實作

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;


public class DataTest {
    public static int INFINITY = 90000;
    public static Map<String,Vertex> vertexMap = new HashMap<String,Vertex>();
    
    static class Edge{
        public Vertex dest;
        public double cost;
        public Edge(Vertex d,double c){
            this.dest = d;
            this.cost = c;
        }
        
    }
    static class Vertex implements Comparable<Vertex>{
        public String name;
        public List<Edge> adj;
        public double dist;
        public Vertex prev;
        public int scratch;
        public boolean visited;
        public Vertex(String nm){
            this.name = nm;
            adj = new ArrayList<Edge>();
            reset();
        }
        public void reset(){
            visited = false;
            dist=DataTest.INFINITY;
        }
        @Override
        public int compareTo(Vertex o) {
            double c = o.dist;
            
            return dist < c ? -1:dist > c ? 1:0;
        }
        
    }
    
    public static void dijkstra(String startName){
        PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();//該隊列以權值升序排列，因為Vertex實作Comparable接口
        Vertex start = vertexMap.get(startName);
        start.dist = 0;
        for(Vertex v:vertexMap.values())
            pq.add(v);
        int seenNum = 0;
        while(!pq.isEmpty()&&seenNum < vertexMap.size()){
            Vertex v = pq.remove();
            System.out.println("v0---->"+v.name+":."+v.dist);
            if(v.scratch != 0)
                continue;
            v.scratch = 1;
            seenNum++;
            for(Edge e:v.adj){ 
                Vertex w = e.dest;
                double v_to_w = e.cost;
                if(w.dist > v.dist + v_to_w){
                    w.dist = v.dist + v_to_w;
                    w.prev = v;
                    pq.remove(w);//出隊
                    pq.add(w);//按優先級插在隊頭，先插入的在隊頭，依次往後
                    
                }
            }
        }
        System.out.println("hello !");
        while(pq.peek() != null ){
            System.out.println(pq.poll());
        }
    }
    
    
    public static void main(String[] args){
        Vertex v0 = new Vertex("v0");
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        
        List<Edge> e0l = v0.adj;
        List<Edge> e1l = v1.adj;
        List<Edge> e2l = v2.adj;
        List<Edge> e3l = v3.adj;
        List<Edge> e4l = v4.adj;
        List<Edge> e5l = v5.adj;
        

        Edge e02 = new Edge(v2,10);
        Edge e04 = new Edge(v4,30);
        Edge e05 = new Edge(v5,100);
        e0l.add(e04);
        e0l.add(e05);
        e0l.add(e02);
        
        Edge e12 = new Edge(v2,5);
        e1l.add(e12);
        
        Edge e23 = new Edge(v3,50);
        e2l.add(e23);
        
        Edge e35 = new Edge(v5,10);
        e3l.add(e35);
        
        Edge e43 = new Edge(v3,20);
        Edge e45 = new Edge(v5,60);
        e4l.add(e43);
        e4l.add(e45);
        /*
        以上代碼建構有向圖  
        v0---->v5:100
        v0----->V4:30
        v0------>V2:10
        V1------>V2:2
        V2------>V3:50
        V3------->V5:10
        v4------->V3:20
        v4------->V5:60
        */    
        vertexMap.put("v0", v0);
        vertexMap.put("v1", v1);
        vertexMap.put("v2", v2);
        vertexMap.put("v3", v3);
        vertexMap.put("v4", v4);
        vertexMap.put("v5", v5);
        
        dijkstra("v0");
    }
}