java - 使用负边权重的 Bellman-Ford 追踪最长路径

Question

我目前正在通过否定所有边权重并运行 Bellman-Ford 算法来寻找有向非循环正加权图中的最长路径。这很好用。

但是，我想打印使用了哪些节点/边的轨迹。我该怎么做？

该程序将节点数、源、目的地和边权重作为输入。输入在 -1 -1 -1 处停止。我的代码如下:

import java.util.Arrays;
import java.util.Vector;
import java.util.Scanner;

public class BellmanFord {
    public static int INF = Integer.MAX_VALUE;

    // this class represents an edge between two nodes
    static class Edge {
        int source; // source node
        int destination; // destination node
        int weight; // weight of the edge
        public Edge() {}; // default constructor
        public Edge(int s, int d, int w) { source = s; destination = d; weight = (w*(-1)); }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int inputgood = 1;
        int tail;
        int head;
        int weight;
        int count = -1;
        Vector<Edge> edges = new Vector<Edge>(); // data structure to hold graph
        int nnodes = input.nextInt();
        while (inputgood == 1) {
            tail = input.nextInt();
            head = input.nextInt();
            weight = input.nextInt();

            if (tail != -1) {
                edges.add(new Edge(tail, head, weight));
                count++;
            }
            if (tail == -1)
                inputgood = 0;
        }
        int start = edges.get(0).source;
        bellmanFord(edges, nnodes, start);
    }

    public static void bellmanFord(Vector<Edge> edges, int nnodes, int source) {
        // the 'distance' array contains the distances from the main source to all other nodes
        int[] distance = new int[nnodes];
        // at the start - all distances are initiated to infinity
        Arrays.fill(distance, INF);
        // the distance from the main source to itself is 0
        distance[source] = 0;
        // in the next loop we run the relaxation 'nnodes' times to ensure that
        // we have found new distances for ALL nodes
        for (int i = 0; i < nnodes; ++i)
            // relax every edge in 'edges'
            for (int j = 0; j < edges.size(); ++j) {
                // analyze the current edge (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):
                // if the distance to the SOURCE node is equal to INF then there's no shorter path from our main source to DESTINATION through SOURCE
                if (distance[edges.get(j).source] == INF) continue;
                // newDistance represents the distance from our main source to DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')
                int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
                // if the newDistance is less than previous longest distance from our main source to DESTINATION
                // then record that new longest distance from the main source to DESTINATION
                if (newDistance < distance[edges.get(j).destination])
                    distance[edges.get(j).destination] = newDistance;
            }
        // next loop analyzes the graph for cycles
        for (int i = 0; i < edges.size(); ++i)
            // 'if (distance[edges.get(i).source] != INF)' means:
            // "
            //    if the distance from the main source node to the DESTINATION node is equal to infinity then there's no path between them
            // "
            // 'if (distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight)' says that there's a negative edge weight cycle in the graph
            if (distance[edges.get(i).source] != INF && distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight) {
                System.out.println("Cycles detected!");
                return;
            }
        // this loop outputs the distances from the main source node to all other nodes of the graph
        for (int i = 0; i < distance.length; ++i)
            if (distance[i] == INF)
                System.out.println("There's no path between " + source + " and " + i);
            else
                System.out.println("The Longest distance between nodes " + source + " and " + i + " is " + distance[i]);
    }
}

Answer 1

您需要稍微修改一下您在 Bellman Ford 实现中所做的事情:

...
int[] lastNode = new int[nnodes];
lastNode[source] = source;
for (int i = 0; i < nnodes; ++i)
    for (int j = 0; j < edges.size(); ++j) {
        if (distance[edges.get(j).source] == INF) continue;
        int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
        if (newDistance < distance[edges.get(j).destination])
        {
            distance[edges.get(j).destination] = newDistance;
            lastNode[edges.get(j).destination] = edges.get(j).source;
        }
    }

然后打印单个路径变为:

static void printPath(int source, int end, int[] lastNodes)
{
    if(source!=end)
        printPath(source, lastNodes[end], lastNodes);
    System.out.print(end+" ");
}

它按从源节点到结束节点的顺序打印路径。