狄杰斯特拉

狄杰斯特拉-邻接矩阵

import java.util.*;
public class Dijiesitela4 {
    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int num=Integer.parseInt(in.nextLine());
        int arr[][]=new int[num][num];
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                arr[i][j]=in.nextInt();
            }
        }
        System.out.println(dijie(arr));
    }
    public static int dijie(int arr[][]){
        int dist[]=new int[arr.length];
        int visit[]=new int[arr.length];
        dist[0]=0;
        visit[0]=1;
        for(int i=1;i<arr.length;i++){
            dist[i]=arr[0][i];
            visit[i]=0;
        }
        for(int i=1;i<arr.length;i++){
            int min=10000;
            int pos=0;
            for(int j=1;j<arr.length;j++){
                if(visit[j]==0 && dist[j]<min){
                    pos=j;
                    min=dist[j];
                }
            }
            for(int j=1;j<arr.length;j++){
                if(dist[pos]+arr[pos][j]<dist[j]){
                    dist[j]=dist[pos]+arr[pos][j];
                }
            }
        }
        return dist[arr.length-1];
    }
}