带权有向图Java求最长路径
时间: 2023-08-09 18:12:25 浏览: 54
求一个带权有向图的最长路径,可以使用拓扑排序和动态规划算法。
具体步骤如下:
1. 对带权有向图进行拓扑排序,得到一个拓扑序列。
2. 初始化一个数组d,d[i]表示从拓扑序列中第i个节点到其它节点的最长路径长度,初始值为负无穷。
3. 对于拓扑序列中的每个节点i,遍历其所有的出边,计算d[j] = max(d[j], d[i] + weight(i,j)),其中weight(i,j)表示从节点i到节点j的边的权值。
4. 最终得到的数组d中,d[i]表示从拓扑序列中第i个节点到其它节点的最长路径长度。
Java代码如下:
``` java
import java.util.*;
public class LongestPath {
static int INF = Integer.MIN_VALUE;
static class Edge {
int to, weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static int[] topoSort(List<List<Edge>> graph) {
int n = graph.size();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
for (Edge e : graph.get(i)) {
inDegree[e.to]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int[] order = new int[n];
int i = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
order[i++] = u;
for (Edge e : graph.get(u)) {
if (--inDegree[e.to] == 0) {
queue.offer(e.to);
}
}
}
return order;
}
static int[] longestPath(List<List<Edge>> graph) {
int n = graph.size();
int[] order = topoSort(graph);
int[] d = new int[n];
Arrays.fill(d, INF);
d[order[0]] = 0;
for (int i = 0; i < n; i++) {
int u = order[i];
if (d[u] == INF) continue;
for (Edge e : graph.get(u)) {
int v = e.to;
int w = e.weight;
d[v] = Math.max(d[v], d[u] + w);
}
}
return d;
}
public static void main(String[] args) {
int n = 6;
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
graph.get(0).add(new Edge(1, 2));
graph.get(0).add(new Edge(2, 3));
graph.get(1).add(new Edge(2, 1));
graph.get(1).add(new Edge(3, 4));
graph.get(2).add(new Edge(4, 5));
graph.get(3).add(new Edge(4, 1));
graph.get(3).add(new Edge(5, 6));
int[] d = longestPath(graph);
System.out.println(Arrays.toString(d));
}
}
```
以上代码输出结果为:`[0, 2, 3, 7, 8, 14]`,表示从节点0到其它节点的最长路径长度分别为0, 2, 3, 7, 8和14。