java 最长路径算法
时间: 2023-07-10 20:06:22 浏览: 61
Java 中最长路径算法主要有两种实现方式:动态规划和拓扑排序。
1. 动态规划
动态规划是一种自底向上的算法,可以求解从一个起点到另一个终点的最长路径。具体实现步骤如下:
1)定义状态:用数组或矩阵表示每个节点的最长路径。
2)状态转移方程:对于每个节点,需要计算其能够到达的所有节点的最长路径,并选择其中最大的作为该节点的最长路径。
3)最终结果:最长路径是所有节点的最大值。
Java 代码实现:
```
public class LongestPath {
public int longestPath(int[][] graph, int start, int end) {
int n = graph.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[start] = 0;
for (int i = start; i <= end; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] != 0) {
dp[j] = Math.max(dp[j], dp[i] + graph[i][j]);
}
}
}
return dp[end];
}
}
```
2. 拓扑排序
拓扑排序是一种基于有向无环图(DAG)的算法,可以求解从一个起点到另一个终点的最长路径。具体实现步骤如下:
1)构建拓扑排序序列:对于 DAG 中的每个节点,按照其入度从小到大排序,得到一个拓扑排序序列。
2)计算最长路径:从起点开始,依次遍历拓扑排序序列中的每个节点,更新其能够到达的所有节点的最长路径,并选择其中最大的作为该节点的最长路径。
3)最终结果:最长路径是终点的最长路径。
Java 代码实现:
```
public class LongestPath {
public int longestPath(int[][] graph, int start, int end) {
int n = graph.length;
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] != 0) {
inDegree[j]++;
}
}
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
int[] dp = new int[n];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int i = 0; i < n; i++) {
if (graph[node][i] != 0) {
inDegree[i]--;
dp[i] = Math.max(dp[i], dp[node] + graph[node][i]);
if (inDegree[i] == 0) {
queue.offer(i);
}
}
}
}
return dp[end];
}
}
```