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

我目前通过否定所有边权和运行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 edges = new Vector(); // 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 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 (ie 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  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]的值是当我们以某种方式创建最优路径时我们从其遍历的节点。

数组通常以更新算法中索引的相同方式更新，以查找数组中的最大元素，即在比较候选路径的适合度与当前路径的适应度时的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 。