一个解决最短路径的经典套路--(迪杰斯特拉)Dijkstra

解题思路:  

    数据结构： 3个数组加一个存储图的二维数组a[][],dis[]存储每个点到原点的最短路径，isno[]存储某点是否为已经是最短路径，qu[]表示某一点的最短路径的前一个点是那个点

    算法：一个大循环套两个小循环                

注意事项:

参考代码:

import java.math.BigInteger;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class Main {

public static int MaxValue = 100000;

//13.25

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

// 输入数据

int n = sc.nextInt();

int yuan = sc.nextInt();

int[][] a = new int[n][n];

int[] dis;

int[] isno;

int[] qu;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

a[i][j] = sc.nextInt();

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (a[i][j] == 0) {

a[i][j] = MaxValue;

}

}

}

// 初始化

dis = new int[n];

Arrays.fill(dis, MaxValue);

isno = new int[n];

Arrays.fill(isno, 0);

qu = new int[n];

Arrays.fill(qu, -1);

// 地杰斯塔拉 大循环套两个循环

dis[yuan] = 0;

isno[yuan] = 1;

int index = yuan;

for (int i = 0; i < n; i++) {

int min = MaxValue;

for (int j = 0; j < n; j++) {

if (isno[j] == 0 && dis[j] < min) {

index = j;

min = dis[j];

}

}

isno[index] = 1;

for (int j = 0; j < n; j++) {

if (isno[j] == 0 && dis[index] + a[index][j] < dis[j] && index != j) {

dis[j] = dis[index] + a[index][j];

qu[j] = index;

}

}

}

//输出

for(int i=0;i<n;i++) {

if(i!=yuan) {

if(dis[i]==100000) {

System.out.print(-1+" ");

}else {

System.out.print(dis[i]+" ");

}

}

}

}

}