2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。输入：graph = [[1,2,3],[0],[0],[0]]。输出：4。
答案 2023-05-12：
大体步骤如下：
1.首先，在 main 函数中调用 shortestPathLength 函数，并将图的邻接表 graph 作为参数传入。
2.在 shortestPathLength 函数中，获取图中节点的个数 n，使用 Floyd 算法计算所有节点之间的最短路径距离，并将结果保存到 distance 二维数组中，同时初始化一个 ans 变量为整型最大值。
3.接下来，初始化一个 dp 数组，其中 dp[i][j] 表示当前状态为 i（二进制表示），当前在节点 j 的情况下，能形成的最短路径长度。同时，对于 dp 数组进行初始化，将所有元素的值设为 -1。
4.循环遍历每个节点 i，从 i 节点出发，通过 process 函数求出访问所有节点的最短路径长度，并更新 ans 的值。
5.在 process 函数中，首先判断当前状态是否已经访问了所有节点，如果是，返回 0 表示已经完成访问。如果 dp 数组中已有对应状态和当前节点的最短路径长度，则直接返回该值，避免重复计算。
6 如果上述条件都不满足，则遍历所有未访问过的且与当前节点 cur 相邻的节点 next，对于这些节点，递归调用 process 函数，并记录访问当前节点 cur 和下一个节点 next 所需的距离 distance[cur][next]，然后将其加上递归得到的 nextAns 值，更新 ans 的值。
7.最后，将计算出的最短路径长度 ans 保存到 dp 数组中，并返回该值。在主函数中输出 ans 的值即为能够访问所有节点的最短路径的长度。
时间复杂度：本算法中使用了 Floyd 算法计算所有节点之间的最短路径，其时间复杂度为 O(n^3)；同时，使用动态规划求解当前状态下访问所有节点的最短路径长度，需要遍历状态空间和邻接表，时间复杂度为 O(2^n * n^2)。因此，总的时间复杂度为 O(n^3 + 2^n * n^2)。
空间复杂度：本算法中使用了一个距离矩阵 distance 数组来存储节点之间的最短路径距离，其空间复杂度为 O(n^2)；同时，使用了一个 dp 数组来记录状态和节点的最短路径长度，其空间复杂度也是 O(2^n * n)。因此，总的空间复杂度为 O(n^2 + 2^n * n)。
go 语言完整代码如下：
package main
import ( "fmt" "math")
func shortestPathLength(graph [][]int) int { n := len(graph) distance := floyd(n, graph) ans := math.MaxInt32 dp := make([][]int, 1<<n) for i := 0; i < (1 << n); i++ { dp[i] = make([]int, n) for j := 0; j < n; j++ { dp[i][j] = -1 } } for i := 0; i < n; i++ { ans = min(ans, process(1<<i, i, n, distance, dp)) } return ans}
func floyd(n int, graph [][]int) [][]int { distance := make([][]int, n) for i := 0; i < n; i++ { distance[i] = make([]int, n) for j := 0; j < n; j++ { distance[i][j] = math.MaxInt32 } } for i := 0; i < n; i++ { distance[i][i] = 0 } for cur := 0; cur < n; cur++ { for _, next := range graph[cur] { distance[cur][next] = 1 distance[next][cur] = 1 } } for jump := 0; jump < n; jump++ { for from := 0; from < n; from++ { for to := 0; to < n; to++ { if distance[from][jump] != math.MaxInt32 && distance[jump][to] != math.MaxInt32 && distance[from][to] > distance[from][jump]+distance[jump][to] { distance[from][to] = distance[from][jump] + distance[jump][to] } } } } return distance}
func process(status, cur, n int, distance, dp [][]int) int { if status == (1<<n)-1 { return 0 } if dp[status][cur] != -1 { return dp[status][cur] } ans := math.MaxInt32 for next := 0; next < n; next++ { if status&(1<<next) == 0 && distance[cur][next] != math.MaxInt32 { nextAns := process(status|(1<<next), next, n, distance, dp) if nextAns != math.MaxInt32 { ans = min(ans, distance[cur][next]+nextAns) } } } dp[status][cur] = ans return ans}
func min(a, b int) int { if a < b { return a } return b}
func main() { graph := [][]int{{1, 2, 3}, {0}, {0}, {0}} ans := shortestPathLength(graph) fmt.Println(ans)}
复制代码
rust 语言完整代码如下：
fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 { let n = graph.len(); let distance = floyd(n, &graph); let mut ans = std::i32::MAX; let mut dp = vec![vec![-1; n]; 1 << n]; for i in 0..(1 << n) { for j in 0..n { dp[i][j] = -1; } } for i in 0..n { ans = ans.min(process(1 << i, i, n, &distance, &mut dp)); } return ans;}
fn floyd(n: usize, graph: &Vec<Vec<i32>>) -> Vec<Vec<i32>> { let mut distance = vec![vec![std::i32::MAX; n]; n]; // 初始化认为都没路 for i in 0..n { for j in 0..n { distance[i][j] = std::i32::MAX; } } // 自己到自己的距离为0 for i in 0..n { distance[i][i] = 0; } // 支持任意有向图，把直接边先填入 for cur in 0..n { for &next in graph[cur].iter() { distance[cur][next as usize] = 1; distance[next as usize][cur] = 1; } } // O(N^3)的过程 // 枚举每个跳板 // 注意! 跳板要最先枚举，然后是from和to for jump in 0..n { for from in 0..n { for to in 0..n { if distance[from][jump] != std::i32::MAX && distance[jump][to] != std::i32::MAX && distance[from][to] > distance[from][jump] + distance[jump][to] { distance[from][to] = distance[from][jump] + distance[jump][to]; } } } } return distance;}
// status : 所有已经走过点的状态// 0 1 2 3 4 5// int// 5 4 3 2 1 0// 0 0 1 1 0 1// cur : 当前所在哪个城市！// n : 一共有几座城// 返回值 : 从此时开始，逛掉所有的城市，至少还要走的路，返回！fn process( status: i32, cur: usize, n: usize, distance: &Vec<Vec<i32>>, dp: &mut Vec<Vec<i32>>,) -> i32 { // 5 4 3 2 1 0 // 1 1 1 1 1 1 // 1 << 6 - 1 if status == (1 << n) - 1 { return 0; } if dp[status as usize][cur] != -1 { return dp[status as usize][cur]; } let mut ans = std::i32::MAX; // status: // 5 4 3 2 1 0 // 0 0 1 0 1 1 // cur : 0 // next : 2 4 5 for next in 0..n { if (status & (1 << next)) == 0 && distance[cur][next] != std::i32::MAX { let next_ans = process(status | (1 << next), next, n, distance, dp); if next_ans != std::i32::MAX { ans = ans.min(distance[cur][next] + next_ans); } } } dp[status as usize][cur] = ans; return ans;}
fn main() { let graph = vec![vec![1, 2, 3], vec![0], vec![0], vec![0]]; let ans = shortest_path_length(graph); println!("{}", ans);}
复制代码
c 语言完整代码如下：
#include <iostream>#include <vector>#include <cstring>#include <algorithm>
using namespace std;
const int N = 15, INF = 0x3f3f3f3f;
int n;int dist[N][N], dp[1 << N][N];
int floyd(vector<vector<int>>& graph){ n = graph.size(); memset(dist, 0x3f, sizeof dist);
for (int i = 0; i < n; i++) for (auto j : graph[i]) dist[i][j] = 1;
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
return 0;}
int dfs(int status, int cur){ if (status == (1 << n) - 1) return 0;
if (dp[status][cur] != -1) return dp[status][cur];
int ans = INF;
for (int next = 0; next < n; next++) if ((status & (1 << next)) == 0 && dist[cur][next] != INF) { int nextAns = dfs(status | (1 << next), next); if (nextAns != INF) ans = min(ans, dist[cur][next] + nextAns); }
return dp[status][cur] = ans;}
int shortestPathLength(vector<vector<int>>& graph) { memset(dp, -1, sizeof dp); floyd(graph);
int ans = INF; for (int i = 0; i < n; i++) ans = min(ans, dfs(1 << i, i)); return ans;}
int main(){ vector<vector<int>> graph = { {1,2,3},{0},{0},{0} }; cout << shortestPathLength(graph) << endl;
return 0;}
复制代码
c++语言完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>
#define N 15#define INF 0x3f3f3f3f
int n;int dist[N][N], dp[1 << N][N];
void floyd(int** graph, int graphSize, int* graphColSize){ n = graphSize; memset(dist, 0x3f, sizeof dist);
for (int i = 0; i < n; i++) for (int j = 0; j < graphColSize[i]; j++) dist[i][graph[i][j]] = 1;
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];}
int dfs(int status, int cur){ if (status == (1 << n) - 1) return 0;
if (dp[status][cur] != -1) return dp[status][cur];
int ans = INF;
for (int next = 0; next < n; next++) if ((status & (1 << next)) == 0 && dist[cur][next] != INF) { int nextAns = dfs(status | (1 << next), next); if (nextAns != INF) ans = ans < dist[cur][next] + nextAns ? ans : dist[cur][next] + nextAns; }
return dp[status][cur] = ans;}
int shortestPathLength(int** graph, int graphSize, int* graphColSize) { memset(dp, -1, sizeof dp); floyd(graph, graphSize, graphColSize);
int ans = INF; for (int i = 0; i < n; i++) ans = ans < dfs(1 << i, i) ? ans : dfs(1 << i, i); return ans;}
int main(){ int graphSize = 4; int graphColSize[] = { 3, 1, 1, 1 }; int** graph = (int**)malloc(sizeof(int*) * graphSize); for (int i = 0; i < graphSize; i++) { graph[i] = (int*)malloc(sizeof(int) * graphColSize[i]); memcpy(graph[i], (int[]) { 0 }, sizeof(int)* graphColSize[i]); } graph[0][0] = 1; graph[0][1] = 2; graph[0][2] = 3;
printf("%d\n", shortestPathLength(graph, graphSize, graphColSize));
for (int i = 0; i < graphSize; i++) free(graph[i]); free(graph);
return 0;}
复制代码
![2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号， 给你一个数组 graph 表示这个图， 其中，graph[i] 是一个列表，由所有与节点 i_Go_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论