我正在尝试解决关于 Dijkstra 算法的 hackerrank 问题- https://www.hackerrank.com/challenges/dijkstrashortreach .我正在使用我自己的 Dijkstra 代码逻辑。尽管我的代码解决了更简单的测试用例,但它在更高的测试用例中失败了。我猜我的代码在某处缺少一些传递性,并且我得到的某些节点的值高于预期值。你能帮我发现我的错误吗? 问题: 输入格式 第一行包含T,表示测试用例的数量。 每个测试用例的第一行有两个整数N,表示图中的节点数和M,表示图中的边数。 接下来的每一行由三个空格分隔的整数 x y r 组成,其中 x 和 y 表示存在无向边的两个节点,r 表示这些对应节点之间的边的长度。 最后一行有一个整数S,表示起始位置。 如果同一对节点之间存在权重不同的边,则将它们视为原样,就像多条边一样。
输出格式 对于每个测试用例,打印一行由 N-1 个空格分隔的整数组成,表示 N-1 个节点距起始位置 S 的最短距离。 对于不可达节点,打印-1
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
for (int i = 0; i < number; i++) {
int n = sc.nextInt();
n++;
int m = sc.nextInt();
int mat[][] = new int[n][n];
for (int v = 0; v < m; v++) {
int r = sc.nextInt();
int c = sc.nextInt();
int weight = sc.nextInt();
mat[r][c] = weight;
mat[c][r] = weight;
}
int dist[] = new int[n];
for (int bb = 0; bb < n; bb++) {
dist[bb] = Integer.MAX_VALUE;
}
Queue<Integer> q = new LinkedList<Integer>();
int source = sc.nextInt();
q.add(source);
dist[source] = 0;
while (!q.isEmpty()) {
int g = q.remove();
for (int k = 1; k < n; k++) {
if (mat[g][k] > 0) { // if mat[g][k]==0, it means there is no edge between the nodes and hence they are not neighbours.
if (g == k)
continue;
if (dist[k] >= dist[g] + mat[k][g]) {
dist[k] = dist[g] + mat[k][g];
q.add(k);
}
}
}
}
for (int f = 1; f < n; f++) {
if (f == source)
continue;
if (dist[f] == Integer.MAX_VALUE)
System.out.print("-1" + " ");
else
System.out.print(dist[f] + " ");
}
System.out.println();
}
}
}
最佳答案
乍一看,你说可以有多个边缘,但据我所知你只存储了一个,总是最新的输入:mat[r][c] = weight;这(和下一行)只是覆盖了可能已经存在且权重较小的边缘。您应该存储两个节点之间的最小加权边。
关于java - 为什么我的 Dijkstra 代码会失败?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37878469/