2023-05-12：存在一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的無向連通圖，圖中的節(jié)點(diǎn)按從 0 到 n - 1 編號(hào)，
給你一個(gè)數(shù)組 graph 表示這個(gè)圖，
其中，graph[i] 是一個(gè)列表，由所有與節(jié)點(diǎn) i 直接相連的節(jié)點(diǎn)組成。
返回能夠訪問所有節(jié)點(diǎn)的最短路徑的長度。
你可以在任一節(jié)點(diǎn)開始和停止，也可以多次重訪節(jié)點(diǎn)，并且可以重用邊。
輸入：graph = [[1,2,3],[0],[0],[0]]。
輸出：4。

答案2023-05-12：

大體步驟如下：

1.首先，在 main 函數(shù)中調(diào)用 shortestPathLength 函數(shù)，并將圖的鄰接表 graph 作為參數(shù)傳入。

2.在 shortestPathLength 函數(shù)中，獲取圖中節(jié)點(diǎn)的個(gè)數(shù) n，使用 Floyd 算法計(jì)算所有節(jié)點(diǎn)之間的最短路徑距離，并將結(jié)果保存到 distance 二維數(shù)組中，同時(shí)初始化一個(gè) ans 變量為整型最大值。

3.接下來，初始化一個(gè) dp 數(shù)組，其中 dp[i][j] 表示當(dāng)前狀態(tài)為 i（二進(jìn)制表示），當(dāng)前在節(jié)點(diǎn) j 的情況下，能形成的最短路徑長度。同時(shí)，對(duì)于 dp 數(shù)組進(jìn)行初始化，將所有元素的值設(shè)為 -1。

4.循環(huán)遍歷每個(gè)節(jié)點(diǎn) i，從 i 節(jié)點(diǎn)出發(fā)，通過 process 函數(shù)求出訪問所有節(jié)點(diǎn)的最短路徑長度，并更新 ans 的值。

5.在 process 函數(shù)中，首先判斷當(dāng)前狀態(tài)是否已經(jīng)訪問了所有節(jié)點(diǎn)，如果是，返回 0 表示已經(jīng)完成訪問。如果 dp 數(shù)組中已有對(duì)應(yīng)狀態(tài)和當(dāng)前節(jié)點(diǎn)的最短路徑長度，則直接返回該值，避免重復(fù)計(jì)算。

6 如果上述條件都不滿足，則遍歷所有未訪問過的且與當(dāng)前節(jié)點(diǎn) cur 相鄰的節(jié)點(diǎn) next，對(duì)于這些節(jié)點(diǎn)，遞歸調(diào)用 process 函數(shù)，并記錄訪問當(dāng)前節(jié)點(diǎn) cur 和下一個(gè)節(jié)點(diǎn) next 所需的距離 distance[cur][next]，然后將其加上遞歸得到的 nextAns 值，更新 ans 的值。

7.最后，將計(jì)算出的最短路徑長度 ans 保存到 dp 數(shù)組中，并返回該值。在主函數(shù)中輸出 ans 的值即為能夠訪問所有節(jié)點(diǎn)的最短路徑的長度。

時(shí)間復(fù)雜度：本算法中使用了 Floyd 算法計(jì)算所有節(jié)點(diǎn)之間的最短路徑，其時(shí)間復(fù)雜度為 O(n^3)；同時(shí)，使用動(dòng)態(tài)規(guī)劃求解當(dāng)前狀態(tài)下訪問所有節(jié)點(diǎn)的最短路徑長度，需要遍歷狀態(tài)空間和鄰接表，時(shí)間復(fù)雜度為 O(2^n * n^2)。因此，總的時(shí)間復(fù)雜度為 O(n^3 + 2^n * n^2)。

空間復(fù)雜度：本算法中使用了一個(gè)距離矩陣 distance 數(shù)組來存儲(chǔ)節(jié)點(diǎn)之間的最短路徑距離，其空間復(fù)雜度為 O(n^2)；同時(shí)，使用了一個(gè) dp 數(shù)組來記錄狀態(tài)和節(jié)點(diǎn)的最短路徑長度，其空間復(fù)雜度也是 O(2^n * n)。因此，總的空間復(fù)雜度為 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)
}

[圖片上傳失敗...(image-faf2ad-1683900706599)]

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];
    // 初始化認(rè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)的過程
    // 枚舉每個(gè)跳板
    // 注意! 跳板要最先枚舉，然后是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 : 所有已經(jīng)走過點(diǎn)的狀態(tài)
// 0 1 2 3 4 5
// int
//        5 4 3 2 1 0
//        0 0 1 1 0 1
// cur : 當(dāng)前所在哪個(gè)城市！
// n : 一共有幾座城
// 返回值 : 從此時(shí)開始，逛掉所有的城市，至少還要走的路，返回！
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);
}

[圖片上傳失敗...(image-b047be-1683900706599)]

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;
}

[圖片上傳失敗...(image-b03aa-1683900706599)]

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;
}

[圖片上傳失敗...(image-1ba791-1683900706599)]