算法分析
注意:若要求任意点i
到任意个点j
的最短距离,只需修改dijkstra方法中的起源位置dist[i] = 0
,以及返回为dist[j]
时间复杂度 $O(n^2+m)$
Java 代码
public class Main{
static int N = 510;
static int n;
static int[][] g = new int[N][N];// 存储每条边
static int[] dist = new int[N];// 存储1号点到每个点的最短距离
static boolean[] st = new boolean[N];
static int INF = 0x3f3f3f3f;//设置无穷大
// 求1号点到n号点的最短路,如果不存在则返回-1
public static int dijkstra()
{
Arrays.fill(dist, INF);
dist[1] = 0;
for(int i = 0;i < n;i++)
{
//1、找到当前未标记过且离源点最近的点
int t = -1;
for(int j = 1;j <= n;j++)
{
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
//2、标记该点已经确定最短距离
st[t] = true;
//3、用该点更新其他点的距离
for(int j = 1;j <= n;j++)
{
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == INF) return -1;
return dist[n];
}
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
for(int i = 1; i <= n; i++ )
Arrays.fill(g[i], INF);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
g[a][b] = Math.min(g[a][b], c);//若有重边,选择最短的
}
System.out.println(dijkstra());
}
}
对比c++和java的模板,感觉还是java简单许多
爱了
写的真不错!! 赞👍
你好,我用PriorityQueue将“找到当前未标记过且离源点最近的点”过程优化为O(logN),反而超时了,为什么?
发下代码
大佬这个图,是咋画的。
电脑自带的画图软件hh
用2号点更新4号点的距离应该是4吧?
是的hh,笔误了,谢谢提醒