题目描述

求一个顶点到其他顶点的最短距离。

总体思路

假设有集合S和集合T,一开始S中只有源点,T中有除源点之外的所有顶点。

每次循环将集合T中距离源点最近的顶点X加入集合S中,得出源点到该顶点的最短距离。再继续一次循环,如果源点到顶点X的距离 + 顶点X到集合T中的顶点的距离 < 集合T中的顶点到源点的距离,那么更新集合T中的顶点到源点的距离为源点到顶点X的距离 + 顶点X到集合T中的顶点的距离。

循环到集合T中没有顶点就结束。

邻接矩阵

public class Dijkstra {
    // matrix是有向图数组,如果顶点间没有相连,那么值设为10000
    public static int[] dijkstra(int[][] matrix, int source) {
        int len = matrix.length;
        int[] shortest = new int[len];
        boolean[] vis = new boolean[len];
        shortest[source] = 0;
        vis[source] = true;
        for (int i = 1; i < len; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int j = 0; j < len; j++) {
                if (!vis[j] && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }

            shortest[index] = min;
            vis[index] = true;

            for (int j = 0; j < len; j++) {
                if (!vis[j] && matrix[source][index] + matrix[index][j] < matrix[source][j]) {
                    matrix[source][j] = matrix[source][index] + matrix[index][j];
                }
            }
        }
        return shortest;
    }
    public static void main(String[] args) {
        int MaxValue = 10000;
        int[][] matrix = {
                {MaxValue,MaxValue,10,MaxValue,30,100},
                {MaxValue,MaxValue,5,MaxValue,MaxValue,MaxValue},
                {MaxValue,MaxValue,MaxValue,50,MaxValue,MaxValue},
                {MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,10},
                {MaxValue,MaxValue,MaxValue,20,MaxValue,60},
                {MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}
        };
        int source = 0;
        int[] path = dijkstra(matrix, source);
        for (int i = 0; i < path.length; i++) {
            if (path[i] == 0) continue;
            if (path[i] == 10000) {
                System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + "不可达");
            }
            else {
                System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + path[i]);
            }
        }
    }
}

邻接链表

public class DijkstraListNode {

    static class Node {
        // 终点
        int to;
        // 权重
        int w;
        // 下一个结点
        Node next;

        public int getTo() {
            return to;
        }

        public void setTo(int to) {
            this.to = to;
        }

        public int getW() {
            return w;
        }

        public void setW(int w) {
            this.w = w;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node(int to, int w, Node node) {
            this.to = to;
            this.w = w;
            this.next = node;
        }

        @Override
        public String toString() {
            return this.to + "," + this.w;
        }
    }
	// 邻接矩阵转邻接链表
    public static Node[] createListNode(int[][] matrix) {
        int len = matrix.length;
        Node[] res = new Node[len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (matrix[i][j] > 0 && matrix[i][j] < 10000) {
                    Node node = new Node(j, matrix[i][j], res[i]);
                    res[i] = node;
                }
            }
        }
        return res;
    }

    public static int[] dijkstra(Node[] path, int source) {
        int len = path.length;
        int[] shortest = new int[len];
        boolean[] vis = new boolean[len];
        shortest[0] = 0;
        vis[0] = true;
        Node temp = path[source];
        while (temp != null) {
            shortest[temp.getTo()] = temp.getW();
            temp = temp.next;
        }
        for (int i = 1; i < len; i++) {
            if (shortest[i] == 0) {
                shortest[i] = 10000;
            }
        }
        for (int i = 1; i < len; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int j = 1; j < len; j++) {
                if (!vis[j] && shortest[j] < min) {
                    min = shortest[j];
                    index = j;
                }
            }
            shortest[index] = min;
            vis[index] = true;
            for (int j = 1; j < len; j++) {
                if (!vis[j]) {
                    Node cur = path[index];
                    while (cur != null) {
                        if (cur.getTo() == j) {
                            break;
                        }
                        cur = cur.next;
                    }
                    if (cur != null) {
                        shortest[j] = Math.min(shortest[j], min + cur.getW());
                    }
                }
            }
        }
        return shortest;
    }

    public static void main(String[] args) {
        int MaxValue = 10000;
        int[][] matrix = {
                {MaxValue,MaxValue,10,MaxValue,30,100},
                {MaxValue,MaxValue,5,MaxValue,MaxValue,MaxValue},
                {MaxValue,MaxValue,MaxValue,50,MaxValue,MaxValue},
                {MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,10},
                {MaxValue,MaxValue,MaxValue,20,MaxValue,60},
                {MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}
        };
        Node[] res = createListNode(matrix);
        int source = 0;
        int[] path = dijkstra(res, source);
        for (int i = 0; i < path.length; i++) {
            if (path[i] == 0) continue;
            if (path[i] == 10000) {
                System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + "不可达");
            }
            else {
                System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + path[i]);
            }
        }

    }
}

结果打印

顶点0->顶点1的最短距离:不可达
顶点0->顶点2的最短距离:10
顶点0->顶点3的最短距离:50
顶点0->顶点4的最短距离:30
顶点0->顶点5的最短距离:60


版权声明:本文为weixin_52272771原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/weixin_52272771/article/details/115548265