用负边权重跟踪使用Bellman-Ford的最长路径 [英] Tracing the longest path using Bellman-Ford with negative edge weights
本文介绍了用负边权重跟踪使用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;
//这个类表示两个节点之间的边缘
static class Edge {
int source; //源节点
int目标; //目标节点
int weight; //边的权重
public Edge（）{}; //默认构造函数
public Edge（int s，int d，int w）{source = s; destination = d;权重=（w *（ - 1））; }
}
public static void main（String [] args）{
Scanner input = new Scanner（System.in）;
int inputgood = 1;
int tail;
int head;
int重量;
int count = -1;
Vector< Edge>边缘=新的矢量< Edge>（）; //数据结构来保存图
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（边缘，nnodes，开始）;
public static void bellmanFord（Vector< Edge> edges，int nnodes，int source）{
//'distance'数组包含从主源到所有其他节点
int [] distance = new int [nnodes];
//在开始时 - 所有距离开始为无穷大
Arrays.fill（distance，INF）;
//从主源到它自身的距离为0
distance [source] = 0;
//在下一个循环中，我们运行放松'nnodes'时间来确保
//我们为所有节点找到新距离
for（int i = 0; i
for（int j = 0; j< edges.size（）; ++ j）{
//分析当前边缘（SOURCE == edges.get（j）.source，DESTINATION == edges.get（j）.destination）：
//如果到SOURCE节点的距离等于INF，则不会有更短的（距离[边缘.get（j）.source] == INF）继续;如果距离我们的主源到DESTINATION的路径通过源
if
// newDistance表示从我们的主源到DESTINATION到源的距离（即使用当前边 - 'edges.get（j）'）
int newDistance = distance [edges.get（j）.source ] + edges.get（j）.weight;
//如果newDistance小于从我们的主源到DESTINATION
的前一个最长距离//然后记录从主源到DESTINATION的新的最长距离
if（newDistance< distance [ edges.get（j）.destination]）
distance [edges.get（j）.destination] = newDistance;
}
//下一个循环分析循环图
for（int i = 0; i< edges.size（）; ++ i）
//'if （distance [edges.get（i）.source]！= INF）'表示：
//
//如果主源节点到DESTINATION节点的距离等于无穷大，那么它们之间没有路径
//
//'if（distance [edges.get（i）.destination]> distance [edges.get（i）.source] + edges.get（i ）.weight）'表示在图
中存在负边权重周期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;
}
//此循环输出从主源节点到图的所有其他节点的距离
for（int i = 0; i< distance.length; ++ i）
if（distance [i] == INF）
System.out.println（+ source +和+ i之间没有路径;
else
System.out.println（节点之间的最长距离+ source +和+ i +是+ distance [i]）;
$ div $解析方案你需要稍微修改你在Bellman Ford实现中做什么：
...
int [] lastNode = new INT [nnodes];
lastNode [source] = source;
for（int i = 0; i
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 +）;
}
按照从源节点到末节点的顺序打印路径。
I'm currently finding the longest path in a directed acyclic positive-weighted graph by negating all edge weights and running Bellman-Ford algorithm. This is working great.
However, I'd like to print the trace of which nodes/edges were used. How can I do that?
The program takes as input the number of nodes, a source, destination and edge weight. Input halts on -1 -1 -1. My code is as follows:
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]);
}
}
解决方案
You need to slightly modify what you do in the Bellman Ford implementation:
...
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;
}
}
Printing individual paths then becomes:
static void printPath(int source, int end, int[] lastNodes)
{
if(source!=end)
printPath(source, lastNodes[end], lastNodes);
System.out.print(end+" ");
}
Which prints the path in order from source node to end node.
这篇关于用负边权重跟踪使用Bellman-Ford的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
