迪杰斯拉算法单源最短路径路径,将起点的邻边节点和距离先加入队列, 与先加入起点到队列的输出结果不一致
来源：12-4 Dijkstra 算法的优化
慕瓜7372772
2022-03-29
这个是我在牛客网刷题的时候遇到的问题
迪杰斯拉算法单源最短路径路径,将起点的邻边节点和距离先加入队列 计算结果是1370, 与先加入起点到队列的输出结果1205不一致
测试用例
81 ,167,[[32,72,724],[63,68,733],[21,36,130],[47,55,445],[14,31,750],[42,78,963],[29,37,209],[4,59,908],[8,13,920],[7,76,855],[4,12,56],[4,67,75],[26,33,741],[58,61,779],[49,59,667],[57,69,118],[21,47,119],[4,46,91],[35,64,60],[32,46,432],[31,45,875],[44,76,74],[53,61,476],[31,72,329],[10,52,72],[28,40,787],[63,81,893],[54,57,681],[33,65,176],[12,76,139],[67,69,83],[32,69,621],[24,32,722],[25,43,581],[19,69,891],[49,69,349],[30,41,502],[32,77,346],[14,16,413],[56,61,690],[26,41,126],[33,52,382],[17,55,705],[24,72,722],[39,49,360],[40,45,811],[58,72,425],[57,68,542],[2,23,502],[28,53,23],[19,55,48],[32,73,636],[48,63,456],[10,30,962],[9,38,556],[68,80,44],[55,74,388],[43,80,319],[34,36,383],[9,75,642],[76,80,954],[10,22,257],[3,62,490],[53,60,233],[31,53,611],[37,45,641],[12,13,352],[20,75,302],[37,41,2],[17,49,895],[27,61,361],[1,57,699],[10,23,42],[11,47,847],[18,65,380],[61,81,710],[33,55,73],[46,67,703],[54,77,154],[44,47,74],[5,34,244],[9,72,118],[9,39,552],[3,19,731],[25,60,869],[50,62,103],[3,56,53],[3,24,88],[25,77,850],[13,32,911],[16,63,580],[7,77,876],[37,63,615],[69,74,179],[10,46,883],[30,43,262],[7,62,22],[3,40,686],[30,53,717],[10,30,267],[5,66,389],[24,48,81],[52,60,28],[2,10,152],[1,57,864],[9,65,428],[23,36,610],[15,49,236],[61,70,840],[13,65,893],[25,32,993],[28,47,461],[29,61,307],[19,48,423],[32,62,640],[30,59,883],[10,61,245],[9,56,765],[74,81,209],[40,68,250],[77,79,175],[45,58,271],[55,76,504],[32,33,700],[32,45,118],[8,44,828],[40,79,398],[35,45,935],[33,78,567],[4,26,161],[9,52,670],[12,46,555],[10,51,760],[2,70,433],[18,68,726],[38,53,759],[12,26,273],[1,75,933],[6,13,690],[6,24,668],[47,66,989],[21,73,647],[53,71,669],[3,15,449],[3,57,123],[31,67,154],[20,61,385],[44,73,393],[19,59,953],[15,36,684],[13,69,48],[70,80,811],[51,53,427],[11,66,599],[32,68,506],[13,56,858],[27,70,447],[12,41,364],[27,75,89],[16,74,412],[16,37,676],[43,49,986],[50,75,187],[26,77,390],[57,66,755],[22,42,502],[2,59,424]]
完整代码如下
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
private HashSet<Edge>[] edges;
class Edge{
int w, weight;
public Edge(int w, int weight){
this.w = w;
this.weight = weight;
}
}
class Node implements Comparable<Node> {
int w, dis;
public Node(int w, int dis){
this.w = w;
this.dis = dis;
}
@Override
public int compareTo(Node other) {
return dis - other.dis;
}
}
private boolean[] visited;
private int[] dis;
private int[] pre;
public int findShortestPath (int n, int m, int[][] graph) {
// djistrak算法
edges = new HashSet[n+1];
for(int i=1; i<=n; i++) {
edges[i] = new HashSet<Edge>();
}
visited = new boolean[n+1];
dis = new int[n+1];
pre = new int[n+1];
Arrays.fill(dis, -1);
// 添加节点和边,权重
for(int i=0; i<m; i++) {
int v = graph[i][0];
int w = graph[i][1];
int weight = graph[i][2];
edges[v].add(new Edge(w, weight));
}
// print();
// 1到n的最短路径
dis[1] = 0;
pre[1] = 1;
PriorityQueue<Node> queue = new PriorityQueue<>();
// for(Edge e : edges[1]) {
// // 将1的边加入到优先队列中
// dis[e.w] = e.weight;
// queue.add(new Node(e.w, dis[e.w]));
// pre[e.w] = 1;
// }
queue.add(new Node(1, 0));
// visited[1] = true;
while(!queue.isEmpty()) {
Node cur = queue.poll();
if (visited[cur.w]) continue;
visited[cur.w] = true;
for(Edge e : edges[cur.w]) {
if (!visited[e.w]) {
// 从原点到w路径大于从cur.w过来
if (dis[cur.w] != -1 && (dis[e.w] == -1 || dis[e.w] > dis[cur.w] + e.weight)) {
dis[e.w] = dis[cur.w] + e.weight;
pre[e.w] = cur.w;
queue.add(new Node(e.w, dis[e.w]));
}
}
}
}
// 1205
return dis[n];
}
private void print(int n){
for(int i=1; i<=n; i++) {
System.out.print("v:" + i + " ==> ");
for(Edge e : edges[i]) {
System.out.print(e.w + ":" + e.weight + " ");
}
System.out.println();
}
}
}
写回答
1回答
-
liuyubobobo
2022-03-29
我没有理解你的问题。什么叫“你那边结果不对？”你的意思是“我这边的结果是对的？你得到的结果和课程中的某些地方矛盾吗？”如果是这样的话，请指出和课程的视频的哪里有冲突，给我一个视频位置，或者课程代码的链接，我来看一下？
课程代码的写法是只添加一个起始点：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/12-Shortest-Path/04-Dijkstra-Algorithm-Optimized/src/Dijkstra.java
如果你只是觉得你的逻辑应该没有问题，可实际却出现了问题，请给我你测试的平台的链接和能复现你错误的代码，我来简单看一下。
==========
测试用例中有重边，导致在外面添加边的时候，dis 的赋值，可能一个更长的距离覆盖了更短的距离。
以下代码可以 ac。改动了三行，相应的地方注释里有 !!! 的标识。
import java.util.*; public class Solution { private HashSet<Edge>[] edges; class Edge{ int w, weight; public Edge(int w, int weight){ this.w = w; this.weight = weight; } } class Node implements Comparable<Node> { int w, dis; public Node(int w, int dis){ this.w = w; this.dis = dis; } @Override public int compareTo(Node other) { return dis - other.dis; } } private boolean[] visited; private int[] dis; private int[] pre; public int findShortestPath (int n, int m, int[][] graph) { // djistrak算法 edges = new HashSet[n+1]; for(int i=1; i<=n; i++) { edges[i] = new HashSet<Edge>(); } visited = new boolean[n+1]; dis = new int[n+1]; pre = new int[n+1]; Arrays.fill(dis, Integer.MAX_VALUE); // !!!这里初始化成 max_value 更方便 // 添加节点和边,权重 for(int i=0; i<m; i++) { int v = graph[i][0]; int w = graph[i][1]; int weight = graph[i][2]; edges[v].add(new Edge(w, weight)); } // print(); // 1到n的最短路径 dis[1] = 0; pre[1] = 1; PriorityQueue<Node> queue = new PriorityQueue<>(); for(Edge e : edges[1]) { // 将1的边加入到优先队列中 dis[e.w] = Math.min(dis[e.w], e.weight); // !!!因为重边，这里要取一个 min queue.add(new Node(e.w, dis[e.w])); pre[e.w] = 1; } visited[1] = true; while(!queue.isEmpty()) { Node cur = queue.poll(); if (visited[cur.w]) continue; visited[cur.w] = true; for(Edge e : edges[cur.w]) { if (!visited[e.w]) { // 从原点到w路径大于从cur.w过来 if (dis[e.w] > dis[cur.w] + e.weight) { // !!! 这个 if 我做了化简 dis[e.w] = dis[cur.w] + e.weight; pre[e.w] = cur.w; queue.add(new Node(e.w, dis[e.w])); } } } } return dis[n]; } }继续加油！：）
022022-03-29
相似问题