迪杰斯特拉算法（Dijkstra）-最短路径

1. 从一个顶点触发，到达所有点的最短路径，利用图的广度优先，将每一个可达顶点的长度与原最小路径比较去完成最小的赋值

public class DijkstraAlgorithm {

    public static void main(String[] args) {
        int N = 65535;
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] maxtrix = {
                {N, 5, 7, N, N, N, 2},
                {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N},
                {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4},
                {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N}

        };
        DGraph graph = new DGraph(vertex, maxtrix);
        graph.dsj(6);
    }
}

class DGraph {

    private char[] vertex;
    private int[][] maxtrix;
    private VisitedVertex vv;

    public DGraph(char[] vertex, int[][] maxtrix) {
        this.vertex = vertex;
        this.maxtrix = maxtrix;
    }
    public void show() {
        for (int i = 0; i < maxtrix.length; i++) {
            System.out.println(Arrays.toString(maxtrix[i]));
        }
    }

    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        update(index);

        for (int j = 1; j < vertex.length; j++) {
            int i = vv.updateArr();
            update(i);
        }
        vv.show();
    }
    public void update(int index) {
        for (int i = 0; i < maxtrix[index].length; i++) {
            int len = vv.getDis(index) + maxtrix[index][i];
            if (!vv.in(index) && len < vv.getDis(i)) {
                vv.updatePre(i, index);
                vv.updateDis(i, len);
            }
        }
    }
}

class VisitedVertex {

    /**
     * 各个顶点访问情况
     */
    public int[] alreadyArr;
    /**
     * 前驱节点小标
     */
    public int[] preVisited;
    /**
     * 距离
     */
    public int[] dis;

    public VisitedVertex(int len, int index) {
        this.alreadyArr = new int[len];
        this.preVisited = new int[len];
        this.dis = new int[len];
        this.alreadyArr[index] = 1;
        Arrays.fill(dis, 65535);
        this.dis[index] = 0;
    }

    public boolean in(int index) {
        return alreadyArr[index] == 0;
    }

    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    public void updatePre(int pre, int index) {
        preVisited[pre] = index;
    }

    public int getDis(int index) {
        return dis[index];
    }

    public int updateArr() {
        int min = 65535;
        int index = 0;
        for (int i = 0; i < alreadyArr.length; i++) {
            if (alreadyArr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
            alreadyArr[index] = 1;
        }
        return index;
    }
    public void show() {
        System.out.println(Arrays.toString(alreadyArr));
        System.out.println(Arrays.toString(preVisited));
        System.out.println(Arrays.toString(dis));
    }
}