2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号， 给你一个数组 graph 表示这个图， 其中，graph[i] 是一个列表，由所有与节点 i 观察
2023-05-12 22:28:07
来源:博客园
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 mainimport ("fmt""math")func shortestPathLength(graph [][]int) int {n := len(graph)distance := floyd(n, graph)ans := math.MaxInt32dp := make([][]int, 1< 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< fn shortest_path_length(graph: Vec>) -> 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> { 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>, dp: &mut Vec>,) -> 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);} #include #include #include #include using namespace std;const int N = 15, INF = 0x3f3f3f3f;int n;int dist[N][N], dp[1 << N][N];int floyd(vector>& 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>& 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> graph = { {1,2,3},{0},{0},{0} }; cout << shortestPathLength(graph) << endl; return 0;} #include #include #include #define N 15#define INF 0x3f3f3f3fint 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;} 关键词：
