迪杰斯特拉算法主要是用廣度優(yōu)先搜索的算法計(jì)算出一個(gè)頂點(diǎn)V到各個(gè)頂點(diǎn)的最短距離
ver表示沒(méi)有走過(guò)的頂點(diǎn)，dis表示頂點(diǎn)V到各個(gè)頂點(diǎn)的距離
首先從ver集合取出取出頂點(diǎn)M，將頂點(diǎn)V的相鄰頂點(diǎn)之間的邊取出，存儲(chǔ)在一個(gè)list1集合里面，將其排序
從list1集合取出最小值的頂點(diǎn)N，并查看VM加上MN的距離是否小于VN的距離，小于則更新，并且從未走的集合中刪除頂點(diǎn)N

public class DijkstraTest {
    public static void main(String[] args) {
        int INF = Integer.MAX_VALUE;
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] edges = {
                {0,   12,   INF,  INF,  INF,  16, 14  },
                {12,  0,    10,   INF,  INF,  7,  INF },
                {INF, 10,   0,    3,    5,    6,  INF },
                {INF, INF,  3,    0,    4,    INF,INF },
                {INF, INF,  5,    4,    0,    2,  8   },
                {16,  7,    6,    INF,  2,    0,  9   },
                {14,  INF,  INF,  INF,  8,    9,  0   },
        };
        Dijkstra dijkstra = new Dijkstra(vertexs,edges);
        dijkstra.getMinTrace('C');
        dijkstra.showMinTrace();
    }
}
class Dijkstra{
    private char[] vertexs;  //頂點(diǎn)集合
    private int[] dist; //目標(biāo)點(diǎn)到各個(gè)點(diǎn)的最短距離
    private int[][] edges; //鄰接矩陣   
    private ArrayList<MData> firstList; //因?yàn)榈辖芩固乩捎脧V度優(yōu)先搜索遍歷，所以這個(gè)存放第一層需要遍歷的點(diǎn)的信息
    private ArrayList<MData> secondList; //在將firstList中取出一個(gè)點(diǎn)查看他的鄰接點(diǎn)的時(shí)候，會(huì)查看我們的出發(fā)點(diǎn)到當(dāng)前頂點(diǎn)的距離是否小于出發(fā)點(diǎn)到該頂點(diǎn)鄰接點(diǎn)的最小距離，如果是，則加入secondList集合，并且更新出發(fā)點(diǎn)到該鄰接點(diǎn)的最小距離
    private HashSet<Character> choice; //沒(méi)有走過(guò)的頂點(diǎn)
    private static final int INF = Integer.MAX_VALUE;
    private HashMap<Character,Integer> vertexToIndex; //將字符轉(zhuǎn)換成其索引，為了方便
    private int startIndex; //出發(fā)點(diǎn)在頂點(diǎn)中的索引

    public Dijkstra(char[] vertexs, int[][] edges) { //初始化工作
        this.vertexs = vertexs;
        this.edges = edges;
        vertexToIndex = new HashMap<>();
        choice = new HashSet<>();
        for (int i = 0; i < vertexs.length; i++) {
            vertexToIndex.put(vertexs[i],i);
            choice.add(vertexs[i]);
        }
        firstList = new ArrayList();
    }
    public void getMinTrace(char start){ //基本上也是初始化工作
        startIndex = vertexToIndex.get(start);
        dist = new int[vertexs.length];
        for (int i = 0; i < dist.length; i++) { //首先將出發(fā)點(diǎn)到各個(gè)頂點(diǎn)的距離設(shè)置未無(wú)窮大
            dist[i] = INF;
        }
        firstList.add(new MData(start,0)); // 首先加入出發(fā)點(diǎn)，便于后面遍歷
        dist[startIndex] = 0; //設(shè)置自身距離為0
        choice.remove(start); //將出發(fā)點(diǎn)從沒(méi)有走過(guò)的頂點(diǎn)里面進(jìn)行刪除
        getMinTrace(); //調(diào)用核心算法
    }
    public void getMinTrace(){
        while (!choice.isEmpty()){ //還有點(diǎn)沒(méi)有走完就繼續(xù)
            secondList = new ArrayList(); //每一輪都需要從新new一下
            while (!firstList.isEmpty()){ //進(jìn)行這一層的遍歷，因?yàn)檫@里面遍歷需要從小打到的遍歷，不然就可以直接將firstList與secondList合并為一個(gè)了
                MData temp = firstList.remove(0); // 取出刪除
                int tempIndex = vertexToIndex.get(temp.next); //獲取 當(dāng)前點(diǎn)的索引
                for (int i = 0; i < edges.length; i++) { //遍歷該頂點(diǎn)的鄰接點(diǎn)了
                    //temp.weight表示當(dāng)前遍歷點(diǎn)到中心點(diǎn)的最小距離，edges[tempIndex][i]表示改變里點(diǎn)到鄰接點(diǎn)的距離，dist[i]表示在這之前中心點(diǎn)到該鄰接點(diǎn)的最小距離
                    if(temp.weight + edges[tempIndex][i] < dist[i] && temp.weight + edges[tempIndex][i] > 0){
                        dist[i] = temp.weight + edges[tempIndex][i];
                        secondList.add(new MData(vertexs[i],dist[i]));
                        choice.remove(vertexs[i]);
                    }
                }
            }
            Collections.sort(secondList); //取出來(lái)的時(shí)候需要從小到大取出，所以需要先進(jìn)性排序
            firstList = secondList; //賦值進(jìn)行下一輪遍歷
        }
    }
    public void showMinTrace(){
        System.out.println(Arrays.toString(dist));
    }
}
class MData implements Comparable<MData> {
    public char next; //需要從這個(gè)點(diǎn)去探索鄰接點(diǎn)
    public int weight; //當(dāng)前（在每一輪循環(huán)中）出發(fā)點(diǎn)到這個(gè)點(diǎn)的最小距離

    public MData(char next, int weight) {
        this.next = next;
        this.weight = weight;
    }

    public int compareTo(MData o) {
        return weight - o.weight;
    }

    @Override
    public String toString() {
        return "MData{next=" + next + ", weight=" + weight + '}';
    }
}