节点的最短路径-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 给定一个图，问走遍所有的点的最短距离是多少

思路：

- 这个题首先考虑一下dfs的做法。假设我们已经到达了m个点，下个点，我们需要枚举所有下个点没有被访问的点，进行访问遍历，直到所有的点都被访问到
- 我们注意到，枚举的过程中，需要枚举所有下个点没有被访问的点，而这个跟先前访问的顺序无关，也就是状态是一个访问集合，和当前到达的点共同组合而成的
- 我们注意到，枚举的过程中，状态是需要重复访问，因此我们利用记忆化搜索，保存中间结果，进行动态规划
- 这里需要注意的，我们可以预先把图形中两两最短距离先求出来缓存起来，这一部分只需要o(n^3)的复杂度
- 子问题是：f(set, last)，set是访问集合，last是当前到达的点，函数值是达到当前状态最短距离
- 这里有个代码的实现方式，集合如何用实现？当然如果想实现一个具备集合特性的数据结构也是可以的，最简单的方式就是用bitset，也就是把集合的信息压缩在一个二进制串中，这个题的数据范围是n<=12，因此一个int就可以表达状态，状态总量是`2^n*n`，因此这个动态规划的时间复杂度是`o(2^n*n^2)`

代码：

```java
class Solution {
	 private int solve(int set, int last, int[][] dist, int[][] cache) {
        if (cache[set][last] != -1) {
            return cache[set][last];
        }

if (set == (1 << dist.length) - 1) {
            return cache[set][last] = 0;
        }

int ret = 0x3fffffff;
        for (int i = 0;i < dist.length;i++) {
            if ((set & (1 << i)) == 0) {
                ret = Math.min(ret, dist[last][i] + solve(set + (1 << i), i, dist, cache));
            }
        }
        return cache[set][last] = ret;
    }

private int[][] calDist(int[][] graph) {
        int[][] dist = new int[graph.length][graph.length];
        for (int i = 0;i < graph.length;i++) {
            for (int j = 0;j < graph.length;j++) {
                dist[i][j] = 0x3fffffff;
            }
        }
        for (int i = 0;i < graph.length;i++) {
            dist[i][i] = 0;
            for (int j = 0;j < graph[i].length;j++) {
                dist[i][graph[i][j]] = 1;
            }
        }
        for (int k = 0;k < graph.length;k++) {
            for (int i = 0;i < graph.length;i++) {
                for (int j = 0;j < graph.length;j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        return dist;
    }

public int shortestPathLength(int[][] graph) {
        int[][] cache = new int[1 << graph.length][graph.length];
        for (int i = 0;i < (1 << graph.length);i++) {
            for (int j = 0;j < graph.length;j++) {
                cache[i][j] = -1;
            }
        }
        int[][] dist = calDist(graph);
        int ret = 0x3fffffff;
        for (int i = 0;i < graph.length;i++) {
            ret = Math.min(ret, solve((1 << i), i, dist, cache));
        }
        return ret;
    }
}
```

该分类下的相关小册推荐：

编程之道-算法面试(下)

数据结构与算法之美

算法面试通关 50 讲

数据结构与算法(下)

编程之道-算法面试(上)

数据结构与算法(上)

业务开发实用算法精讲