【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总
广度优先搜索 状态压缩

LeetCode847 访问所有节点的最短路径

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 1：
输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]
示例 2：
输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]
参数范围：
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] 不包含 i
如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
输入的图总是连通图

广度优先搜索

需要记录那些节点已经访问，用状态压缩 (1 << i )表示第i个节点已访问。
还要记录此路径的最后节点。
这两个状态相同，后面的路径则相同。 由于是广度优先搜索，所以路径短的先处理，每个状态只会处理一次。
vDis 记录各状态的最短路径数。
que 记录状态。
状态数2ⁿn ，访问状态2ⁿ，终点状态O(n)。
时间复杂度：对于每种访问状态，转移方程的复杂度是 总边数，不超过n$\times$ n 。故总时间复杂度O(n$\times$n)。

核心代码

class Solution { public: 	int shortestPathLength(vector<vector<int>>& graph) { 		m_c = graph.size(); 		m_iMaskCount = 1 << m_c; 		for (int i = 0; i < m_c; i++) 		{ 			BFS(graph, i); 		} 		return m_iRet; 	} 	void BFS(vector<vector<int>>& neiBo,int start) 	{ 		vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay)); 		queue<pair<int, int>> que; 		auto Add = [&](int node, int iPreMask,int iNew) 		{ 			const int iMask = iPreMask | (1 << node); 			if (vDis[node][iMask] <= iNew ) 			{ 				return ; 			} 			vDis[node][iMask] = iNew; 			que.emplace(node, iMask); 		}; 		Add( start,0, 0); 		while (que.size()) 		{ 			auto [preNode, preMask] = que.front(); 			const int iNew = vDis[preNode][preMask]+1; 			que.pop(); 			for (const auto& next : neiBo[preNode]) 			{ 				Add(next, preMask, iNew); 			} 		} 		for (const auto& v : vDis) 		{ 			m_iRet = min(m_iRet, v.back()); 		} 	} 	const int m_iNotMay = 100'000; 	int m_c, m_iMaskCount; 	int m_iRet = m_iNotMay; }; 

测试用例

template<class T> void Assert(const T& t1, const T& t2) { 	assert(t1 == t2); }  template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { 	if (v1.size() != v2.size()) 	{ 		assert(false); 		return; 	} 	for (int i = 0; i < v1.size(); i++) 	{ 		Assert(v1[i], v2[i]); 	}  }  int main() {	 	vector<vector<int>> graph; 	{ 		Solution sln; 		graph = { {1,2,3},{0},{0},{0} }; 		auto res = sln.shortestPathLength(graph); 		Assert(res, 4); 	}  	{ 		Solution sln; 		graph = { {1},{0,2,4},{1,3,4},{2},{1,2} }; 		auto res = sln.shortestPathLength(graph); 		Assert(res, 4);  	} 	 }  

动态规划

节点的距离用多源路径的最短距离。

动态规划的状态表示

mask&(1 << next)表示经过了next节点。
vDis[node][mask] 有以下两种含义：
一， 以node结尾，经过mask指定节点的最短路径经过的节点数。
二，以node结尾，且只经过node节点一次,经过mask指定节点的最短路径经过的节点数。
含义二，如果存在，则是含义二，否则是含义一。 必须枚举所有符合含义二的可能。

动态规划的转移方程

vDis[next][maks|next]= MinSelf${}_{next=0}^{m_c-1}$vDis[i][mask]+距离(i,next)
vDis[i][mask] 必须合法，且mask不包括next节点

动态规划的填表顺序

mask从1到大，确保动态规划的无后效性。某路径的编码是mask，经过新节点next后，新编码为iNewMask。则iNewMask-mask = 1 << next
1 << next 恒大于0。

动态规划的初始值

全部为不存在的数

动态规划的返回值

Min${}_{j=0}^{m_c-1}$vDis[j].back() -1

证明

将最短路径的重复节点删除，保留任意一个。删除后为: i${}_1$ i${}_2$ …i${}_n$ 。任意i${}_k$到i${}_{k+1}$的路径一定是最短，否则替换成最短。直接枚举，12! 超时。 用动态规划，共2ⁿn种状态，空间复杂度O(2ⁿn)，每种状态转移时间复杂度O(n)，故总时间复杂度O(2ⁿnn)。

代码

//多源码路径 template<class T, T INF = 1000 * 1000 * 1000> class CFloyd { public: 	CFloyd(const  vector<vector<T>>& mat) 	{ 		m_vMat = mat; 		const int n = mat.size(); 		for (int i = 0; i < n; i++) 		{//通过i中转 			for (int i1 = 0; i1 < n; i1++) 			{ 				for (int i2 = 0; i2 < n; i2++) 				{ 					//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 					m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]); 					//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 				} 			} 		} 	}; 	vector<vector<T>> m_vMat; };  class Solution { public: 	int shortestPathLength(vector<vector<int>>& graph) { 		m_c = graph.size(); 		m_iMaskCount = 1 << m_c; 		vector<vector<int>> mat(m_c, vector<int>(m_c, 1000 * 1000 * 1000)); 		for (int i = 0; i < m_c; i++) 		{ 			for (const auto& j : graph[i]) 			{ 				mat[i][j] = 1; 			} 		} 		CFloyd floyd(mat); 		vector<vector<int>> vDis(m_c, vector<int>(m_iMaskCount, m_iNotMay)); 		for (int i = 0; i < m_c; i++) 		{	 			vDis[i][1 << i] = 1; 		} 		for (int mask = 1; mask < m_iMaskCount; mask++) 		{ 			for (int i = 0; i < m_c; i++) 			{ 				if (vDis[i][mask] >= m_iNotMay) 				{ 					continue; 				} 				for (int next = 0 ;next < m_c ;next++ ) 				{ 					if ((1 << next) & mask) 					{ 						continue;//已经访问 					} 					const int iNewMask = (1 << next) | mask; 					vDis[next][iNewMask] = min(vDis[next][iNewMask], vDis[i][mask] + floyd.m_vMat[i][next]); 				} 			} 		} 		int iRet = m_iNotMay; 		for (const auto& v : vDis) 		{ 			iRet = min(iRet, v.back()); 		} 		return iRet-1; 	} 	const int m_iNotMay = 100'000; 	int m_c, m_iMaskCount;  }; 

2023年1月

class Solution {
public:
int shortestPathLength(vector<vector>& graph) {
auto Add = [this](int iMask, int iPos, int iOpeNum)
{
if (INT_MAX != m_vMaskPosMinOpe[iMask][iPos])
{
return;
}
m_vQue.emplace_back(iMask, iPos);
m_vMaskPosMinOpe[iMask][iPos] = iOpeNum;
};
m_c = graph.size();
for (int i = 0; i < sizeof(m_vMaskPosMinOpe) / sizeof(m_vMaskPosMinOpe[0]); i++)
{
for (int j = 0; j < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); j++)
{
m_vMaskPosMinOpe[i][j] = INT_MAX;
}
}
for (int i = 0; i < m_c; i++)
{
Add(1 << i, i, 0);
}
for (int i = 0; i < m_vQue.size(); i++)
{
const int iMask = m_vQue[i].first;
const int iPos = m_vQue[i].second;
for (auto& next : graph[iPos])
{
int iNewMask = iMask | (1 << next);
Add(iNewMask, next, m_vMaskPosMinOpe[iMask][iPos] + 1);
}
}
int iMin = INT_MAX;
for (int i = 0; i < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); i++)
{
iMin = min(iMin, m_vMaskPosMinOpe[(1 << m_c) - 1][i]);
}
return iMin;
}
vector<std::pair<int,int>> m_vQue;
int m_vMaskPosMinOpe[1 << 12 ][12];
int m_c;
};

2023年8月

class Solution {
public:
int shortestPathLength(vector<vector>& graph) {
auto Add = [this](int iMask, int iPos, int iOpeNum)
{
if (INT_MAX != m_vMaskPosMinOpe[iMask][iPos])
{
return;
}
m_vQue.emplace_back(iMask, iPos);
m_vMaskPosMinOpe[iMask][iPos] = iOpeNum;
};
m_c = graph.size();
for (int i = 0; i < sizeof(m_vMaskPosMinOpe) / sizeof(m_vMaskPosMinOpe[0]); i++)
{
for (int j = 0; j < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); j++)
{
m_vMaskPosMinOpe[i][j] = INT_MAX;
}
}
for (int i = 0; i < m_c; i++)
{
Add(1 << i, i, 0);
}
for (int i = 0; i < m_vQue.size(); i++)
{
const int iMask = m_vQue[i].first;
const int iPos = m_vQue[i].second;
for (auto& next : graph[iPos])
{
int iNewMask = iMask | (1 << next);
Add(iNewMask, next, m_vMaskPosMinOpe[iMask][iPos] + 1);
}
}
int iMin = INT_MAX;
for (int i = 0; i < sizeof(m_vMaskPosMinOpe[0]) / sizeof(m_vMaskPosMinOpe[0][0]); i++)
{
iMin = min(iMin, m_vMaskPosMinOpe[(1 << m_c) - 1][i]);
}
return iMin;
}
vector<std::pair<int,int>> m_vQue;
int m_vMaskPosMinOpe[1 << 12 ][12];
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。