Dijkstra算法实现

Dijkstra.java

package graph;

public class Dijkstra {
    // 节点数目
    int size;
    // 定点信息
    String[] nodes;
    // 保存边的信息
    int[][] edges;

    private int[] isMarked;   // 节点确认
    private String[] path;    // 源到节点的路径信息
    private int[] distance;   // 源到节点的距离


    public Dijkstra() {
        init();

        isMarked = new int[size];
        path = new String[size];
        distance = new int[size];

        for (int i = 0; i < size; i++) {
            path[i] = "";
            distance[i] = Integer.MAX_VALUE;
        }
    }

    private void init() {
        nodes = new String[]{"AA", "A", "B", "C", "D", "E", "F", "G", "H", "M", "K", "N"};
        final int AA = 0, A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, M = 9, K = 10, N = 11;
        size = nodes.length;

        edges = new int[size][size];
        edges[AA][A] = 3;
        edges[AA][B] = 2;
        edges[AA][C] = 5;
        edges[A][AA] = 3;
        edges[A][D] = 4;
        edges[B][AA] = 2;
        edges[B][C] = 2;
        edges[B][G] = 2;
        edges[B][E] = 3;
        edges[C][AA] = 5;
        edges[C][E] = 2;
        edges[C][B] = 2;
        edges[C][F] = 3;
        edges[D][A] = 4;
        edges[D][G] = 1;
        edges[E][B] = 3;
        edges[E][C] = 2;
        edges[E][F] = 2;
        edges[E][K] = 1;
        edges[E][H] = 3;
        edges[E][M] = 1;
        edges[F][C] = 3;
        edges[F][E] = 2;
        edges[F][K] = 4;
        edges[G][B] = 2;
        edges[G][D] = 1;
        edges[G][H] = 2;
        edges[H][G] = 2;
        edges[H][E] = 3;
        edges[K][E] = 1;
        edges[K][F] = 4;
        edges[K][N] = 2;
        edges[M][E] = 1;
        edges[M][N] = 3;
        edges[N][K] = 2;
        edges[N][M] = 3;

    }

    private void search(int idx) {
        path[idx] = nodes[idx];
        distance[idx] = 0;

        do {
            updateNode(idx);
            idx = getShortest();
        } while (idx != -1);
    }

     /**
     * 更新邻接点的权重
     * @param node 要更新的节点
     */
    private void updateNode(int node) {
        isMarked[node] = 1;   // 加入中心标识
        System.out.println(path[node]);

        // 扫描邻接点
        for (int i = 0; i < size; i++) {
            if (edges[node][i] > 0) {
                // 计算源节点到i节点的权重
                int distant = distance[node] + edges[node][i];
                if (distant < distance[i]) {
                    distance[i] = distant;
                    path[i] = path[node] + "--->" + nodes[i];
                }
            }
        }
    }

    /**
     * 获取邻接点中权重最小的
     */
    private int getShortest() {
        int index = -1;

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            if (isMarked[i] == 1) {
                continue;
            }

            if (distance[i] < min) {
                min = distance[i];
                index = i;
            }
        }
        return index;
    }


    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra();

        // 可从任一节点开始
        dijkstra.search(0);
    }

}