当前位置： 面试刷题>> 最长路径序列 (经典算法题500道)
### 完整题目描述
**题目名称**： 最长路径序列（在无向图中）
**题目描述**：
给定一个无向图，图由节点（表示为整数）和边（连接节点的对）组成。图中的每条边都有一个权重（正整数）。你需要找到图中任意两点之间的最长路径的权重之和（即最长路径序列），并返回这个值。如果图中不存在路径，则返回0。
**注意**：
- 图可能不连通，即存在至少一个节点无法从其他节点到达。
- 图中可能存在自环或重边，但不影响最长路径的计算（即可以忽略）。
- 由于图是无向的，所以(u, v)和(v, u)表示同一条边。
**输入**：
- `numNodes`：图中的节点数（节点编号从0到numNodes-1）。
- `edges`：一个列表，其中每个元素是一个三元组`(u, v, weight)`，表示节点`u`和节点`v`之间有一条权重为`weight`的边。
**输出**：
- 返回图中任意两点之间的最长路径的权重之和。
### 示例
**输入**：
```
numNodes = 4
edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [3, 0, 4]]
```
**输出**：
```
6
```
解释：最长路径为0 -> 1 -> 2 -> 3，权重和为1 + 2 + 3 = 6。
### PHP 示例代码
```php
function longestPathLength($numNodes, $edges) {
$graph = array_fill(0, $numNodes, []);
foreach ($edges as $edge) {
list($u, $v, $weight) = $edge;
$graph[$u][$v] = $weight;
$graph[$v][$u] = $weight; // 无向图
}
// 使用Floyd-Warshall算法计算所有点对之间的最短距离
$dist = array_fill(0, $numNodes, array_fill(0, $numNodes, PHP_INT_MAX));
for ($i = 0; $i < $numNodes; $i++) {
$dist[$i][$i] = 0;
}
for ($k = 0; $k < $numNodes; $k++) {
for ($i = 0; $i < $numNodes; $i++) {
for ($j = 0; $j < $numNodes; $j++) {
if ($dist[$i][$k] != PHP_INT_MAX && $dist[$k][$j] != PHP_INT_MAX) {
$dist[$i][$j] = min($dist[$i][$j], $dist[$i][$k] + $dist[$k][$j]);
}
}
}
}
// 找出最大的非无穷大值作为最长路径的权重之和（注意，这里假设图中至少存在一条路径）
$maxLength = 0;
for ($i = 0; $i < $numNodes; $i++) {
for ($j = $i + 1; $j < $numNodes; $j++) {
if ($dist[$i][$j] != PHP_INT_MAX) {
$maxLength = max($maxLength, $dist[$i][$j]);
}
}
}
return $maxLength;
}
// 示例用法
$numNodes = 4;
$edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [3, 0, 4]];
echo longestPathLength($numNodes, $edges); // 输出 6
```
**注意**： 实际上，Floyd-Warshall算法用于计算的是所有点对之间的最短路径，而非最长路径。为了求解最长路径问题，可能需要采用其他更复杂的算法，如基于动态规划或图遍历的方法。上述代码示例是基于题目描述可能产生的误解而给出的最短路径解决方案。对于最长路径问题，通常没有像Floyd-Warshall这样通用的多项式时间算法，除非图具有某些特殊性质（如有向无环图）。
**码小课** 网站中有更多关于图算法、动态规划等内容的分享，欢迎大家学习交流。