Bellman-Ford算法中距离数组初始化为0

Question

在使用Bellman-Ford算法解决最短路径问题时，我发现很难理解为什么在某些问题中距离数组被初始化为0。

根据algo，只有源顶点将被初始化为0，其他顶点将被初始化为正无穷大。

然而，我注意到以下问题仅在距离[]初始化为0时通过了所有测试用例。

问题

我的代码

// Link to this code: https://cses.fi/paste/03babebf2de8fff2298001/

//package com.graph;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class CycleFinding {
 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args)  throws Exception {
        new CycleFinding().run();
    }
 
    public void run() throws Exception {
    
        StringTokenizer tokens = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(tokens.nextToken());
        int m = Integer.parseInt(tokens.nextToken());
        
        Edge[] edgeArr = new Edge[m];
        int idx = 0;
        while( idx < m ) {
            StringTokenizer edgeTokens = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(edgeTokens.nextToken());
            int b = Integer.parseInt(edgeTokens.nextToken());
            double c = Double.parseDouble(edgeTokens.nextToken());
 
            Edge edge = new Edge(a, b, c);
            edgeArr[idx++] = edge;          
        }
        detectCycle(n, m, edgeArr);
        out.flush();
    }
 
    public void detectCycle( int n , int m , Edge[] edgeArr ) {
        
        double[] distance = new double[n+1];
//      Arrays.fill(distance, Double.POSITIVE_INFINITY);
        int[] parent = new int[n+1];
        Arrays.fill(parent, -1);
        
        int src =3;
        distance[src] = 0;
        
        int x = Integer.MIN_VALUE;
        
        for(int i=1;i<=n;i++) {
            x = Integer.MIN_VALUE;
            for(Edge edge : edgeArr) {
                if( distance[edge.to] > distance[edge.from] + edge.length ) {
                    distance[edge.to] = distance[edge.from] + edge.length; 
                    parent[edge.to] = edge.from;
                    x = edge.to;
                }
            }
        }
 
        if( x == Integer.MIN_VALUE ) {
            out.println("NO");
        }else {
            
            for(int i=1;i<=n;i++) 
                x =parent[x];
        
            ArrayList<Integer> cycle = new ArrayList<>();
            for(int v = x;; v = parent[v])
            {
               cycle.add(v);
               if (v == x && cycle.size() > 1)
                        break;
            }
                // Reverse cycle[]
            Collections.reverse(cycle);
            out.println("YES");
            StringBuilder builder = new StringBuilder();
            for(int v : cycle) {
                builder.append(v);
                builder.append(" ");
            }
            out.println(builder.toString());
        }       
    }
    
    public List<Integer> printCycle(double[] distance){
        List<Integer> list = new ArrayList<Integer>();
                
        
        return list;
    }
    
    
 static class Edge{
     int from;
     int to;
     double length;
 
     public Edge(int from, int to, double length) {
         this.from = from;
         this.to = to;
         this.length = length;
     }
 }
}

在线搜索后，我发现在以下情况下，距离[]应初始化为0

• 当需要多源最短路径时。

请帮助我理解，何时用0初始化距离数组，何时用无穷大初始化距离数组。

Answer 1

这也是一个多源Bellman-Ford案例。这是因为如果我们在一个特定的源上运行算法，图可能不会达到负循环（图可能没有连接，或者只是没有从该源到负循环的定向路径）。您还可以在一些文本中找到这种方法，例如创建新的源并连接所有具有权重为零的边的节点。如果存在负循环，则在从新来源运行经典贝尔曼福特后会检测到。

事实上，可以使用任何值初始化所有距离，但所有节点都应该具有相同的初始距离。