【笔记】数据结构与算法之Dijkstra（最短路）
第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
所有边权均为正值，请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
import java.util.Scanner;
/*
适用于稠密的边
*/
public class Main {
private static int N= 510;
static int n,m;
//为稠密阵所以用邻接矩阵存储
static int[][] g = new int;
// distance 距离
static int [] dist = new int;
//statue判断当前的点是不是最终确定的最短点
staticboolean [] st = new boolean;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//首先把每个点设置无限大
g = 0x3f3f3f;
}
}
while (m-- >0){
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
// 如果重边了 保留最短的那条
g = Math.min(g,z);
}
System.out.println(dijkstra());
}
private static int dijkstra() {
//初始化
for (int i = 0; i < N; i++) {
dist = 0x3f3f3f;
}
// 第一个点到自己的距离是0
dist = 0;
for (int i = 0; i < n; i++) {
// 由于每一次都要找到还没有确定最短路距离的所有点中，距离当前的点最短的点。
// t = - 1是为了在st这个集合中找第一个点更新时候的方便所设定的。
int t = -1;
for(int j = 1;j<=n;j++){
//当前的j没有用过如果t是-1的话 或者dt > djt就等于j
if (!st && (t==-1 || dist>dist)){
t = j;
}
}
if (t==n){
break;
}
st = true;
//找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
for(int j = 1;j<=n;j++){
dist = Math.min(dist,dist+g);
}
}
if(dist==0x3f3f3f)return -1;
return dist;
}
}
终于考试完考察完了，抽空学习一下{:301_986:} 收藏一下，有空就学习一下， 收藏一下，有空学习 感谢楼主分享
页:
[1]