迪杰斯特拉算法

/**
 * 边表的节点
 */
class EdgeNode{
    //节点编号
    public int no;
    // 权重
    public int weight;
    // 下一个边
    public EdgeNode next;
    public EdgeNode(int no,int weight){
        this.no = no;
        this.weight = weight;
        next = null;
    }


    @Override
    public String toString() {
        return "EdgeNode{" +
                "no=" + no +
                '}';
    }
}
public class LinkedGraph {
    public EdgeNode[] graph;
    public int dist[];
    public int path[];
    public int set[];
    public LinkedGraph(int n,int[][] edge){
        graph = new EdgeNode[n];
        for(int i =0;i<edge.length;i++){
            int first = edge[i][0];
            int second = edge[i][1];
            // 权重
            int weight = edge[i][2];
            EdgeNode node = new EdgeNode(second,weight);
            /**
             * graph[first]本身就是first的一个邻居节点
             */
            if(graph[first] == null){
                graph[first] = node;
            }else{
                node.next = graph[first];
                graph[first] = node;
            }
        }
    }
    /**
     * 从k出发，得到最短路径
     */
    public void dijkstra(int k){
        int n = graph.length;
        dist = new int[n];
        path = new int[n];
        set = new int[n];
        //初始化
        for(int i=0;i<n;i++){
            dist[i] = Integer.MAX_VALUE;
            path[i] = -1;
            set[i] = 0;
        }
        dist[k] = 0;
        path[k] = 0;
        set[k] = 1;
        // 更新k的邻居节点
        update(k);


        int cnt = 1;
        //  正式执行dijstra主体代码
        while(cnt < n){
            //选择最小距离的节点
            int nodeIdx = selectMinDist();
            if(nodeIdx==-1){
                break;
            }
            set[nodeIdx] = 1;
            cnt++;


            // 更新dist，path
            update(nodeIdx);
        }
    }


    /**
     * 选择距离最小且还没有被确定最短距离的节点
     * @return
     */
    private int selectMinDist(){
        int min = -1;
        for(int i=0;i<dist.length;i++){
            if(set[i]==0){
                if(min == -1){
                    min = i;
                }else if(dist[i]< dist[min]){
                    min = i;
                }
            }
        }
        return min;
    }
    /**
     * 从k节点出发，更新dist和path
     */
    private void update(int k){
        EdgeNode neighbor = graph[k];
        while(neighbor!=null){
            if(set[neighbor.no]==0){
                int newDist = dist[k]+neighbor.weight;
                if(newDist < dist[neighbor.no]){
                    dist[neighbor.no] = newDist;
                    path[neighbor.no] = k;
                }
            }
            neighbor = neighbor.next;
        }
    }
}


//Main函数 调用
public class Main {
    public static void main(String[] args) {
        // {0,1,4} 表示从0 到 1 存在一条权重为4的边
        int[][] edge = new int[][]{{0,1,4},{0,3,6},{0,2,6},{1,2,1},{1,4,7},{2,4,6},{2,5,4},{3,2,2},{3,5,5},{4,6,6},{5,4,1},{5,6,8}};
        LinkedGraph graph = new LinkedGraph(7,edge);
        graph.dijkstra(0);
        System.out.println("dist数组");
        for(int i=0;i<graph.dist.length;i++){
            System.out.printf("%d \t",graph.dist[i]);
        }
        System.out.println();


        System.out.println("path数组");
        for(int i=0;i<graph.path.length;i++){
            System.out.printf("%d \t",graph.path[i]);
        }
        System.out.println();
    }
}