题目描述
n 个 点,m 条边
其中 1 号点为 起点
然后求 1 号点到其他点的 最短距离的最大值
算法1
(朴素版 dijkstra 算法) $O(n^2)$
套模板,
时间复杂度
$O(n^2)$
参考文献
算法基础课模板
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int n;
static int m;
static int N=110;
static int INF=0x3f3f3f3f;
static int [][]g=new int[N][N];
static int[]dist=new int[N];
static boolean[] st=new boolean[N];
public static void dijkstra(){
Arrays.fill(dist,INF);
dist[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t])){
t=j;
}
}
st[t]=true;
for(int j=1;j<=n;j++){
dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
String[] strs=reader.readLine().split(" ");
n=Integer.parseInt(strs[0]);
m=Integer.parseInt(strs[1]);
int a,b,c;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
g[i][j]=0;
}else{
g[i][j]=INF;
}
}
}
for(int i=0;i<m;i++){
strs=reader.readLine().split(" ");
a=Integer.parseInt(strs[0]);
b=Integer.parseInt(strs[1]);
c=Integer.parseInt(strs[2]);
g[a][b]=c;
g[b][a]=c;
}
dijkstra();
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(res,dist[i]);
}
if(res==INF){
System.out.println("-1");
}else{
System.out.println(res);
}
reader.close();
}
}
算法2
spfa 算法
时间复杂度 $O(m)$
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int n;
static int m;
static int N=110;
static int M=200*2+10;
static int INF=0x3f3f3f3f;
// 存图
static int []h= new int [N];
static int[]e =new int[M];
static int[]ne =new int[M];
static int[]w=new int[M];
static int idx;
static int[]dist=new int[N];
static boolean[] st=new boolean[N];
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
public static void spfa(){
Queue<Integer>queue=new LinkedList<>();
Arrays.fill(dist,INF);
st[1]=true;
dist[1]=0;
queue.offer(1);
while(!queue.isEmpty()){
int t=queue.poll();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j] > dist[t] + w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
queue.offer(j);
st[j]=true;
}
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
String[] strs=reader.readLine().split(" ");
n=Integer.parseInt(strs[0]);
m=Integer.parseInt(strs[1]);
int a,b,c;
Arrays.fill(h,-1);
for(int i=0;i<m;i++){
strs=reader.readLine().split(" ");
a=Integer.parseInt(strs[0]);
b=Integer.parseInt(strs[1]);
c=Integer.parseInt(strs[2]);
add(a,b,c);
add(b,a,c);
}
spfa();
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
res=Math.max(res,dist[i]);
}
if(res==INF){
System.out.println("-1");
}else{
System.out.println(res);
}
reader.close();
}
}