用具有负边权值的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+" ");
}

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

Answer 2

图形算法的常见解决方案是维护parent[edge] -> edge映射。对于边e，当我们以某种方式创建最优路径时，parent[e]的值是我们从其遍历到e的节点。

更新数组的方式通常与在算法中更新索引以查找数组中最大的元素的方式相同，即在比较候选路径和当前路径的适应度时，在if条件内。

在你的例子中，它在这里：

if (newDistance < distance[edges.get(j).destination]) {
   distance[edges.get(j).destination] = newDistance;
   parent[edges.get(j).destination] = edges.get(j).source;
}

在计算parent映射之后，您可以获取目标节点并遍历它，递归地构建一个数组[dest, parent[dest], parent[parent[dest]], ... source。