哈尔滨市建筑企业管理站,安阳安强网络科技有限公司,湖南住房城乡建设厅网站,做数据分析好看的网站作者推荐
视频算法专题
本文涉及知识点
动态规划汇总 广度优先搜索 状态压缩
LeetCode847 访问所有节点的最短路径
存在一个由 n 个节点组成的无向连通图#xff0c;图中的节点按从 0 到 n - 1 编号。 给你一个数组 graph 表示这个图。其中#xff0c;graph[i] 是一个列…作者推荐
视频算法专题
本文涉及知识点
动态规划汇总 广度优先搜索 状态压缩
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 记录状态。 时间复杂度O(n2nn) 枚举起点O(n) 枚举状态数O(2^n) 每个状态处理。
核心代码
class Solution {
public:int shortestPathLength(vectorvectorint 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(vectorvectorint neiBo,int start){vectorvectorint vDis(m_c, vectorint(m_iMaskCount, m_iNotMay));queuepairint, 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 100000;int m_c, m_iMaskCount;int m_iRet m_iNotMay;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ vectorvectorint 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 n e x t 0 m c − 1 \Large_{next0}^{m_c-1} next0mc−1vDis[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 \Large_{j0}^{m_c-1} j0mc−1vDis[j].back() -1
证明
将最短路径的重复节点删除保留任意一个。删除后为: i 1 \Large_1 1 i 2 \Large_2 2 …i n \Large_n n 。任意i k \Large_k k到i k 1 \Large_{k1} k1的路径一定是最短否则替换成最短。直接枚举12! 超时。 用动态规划共2nn种状态空间复杂度O(2nn)每种状态转移时间复杂度O(n)故总时间复杂度O(2nnn)。
代码
//多源码路径
templateclass T, T INF 1000 * 1000 * 1000
class CFloyd
{
public:CFloyd(const vectorvectorT 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]中转的最短距离}}}};vectorvectorT m_vMat;
};class Solution {
public:int shortestPathLength(vectorvectorint graph) {m_c graph.size();m_iMaskCount 1 m_c;vectorvectorint mat(m_c, vectorint(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);vectorvectorint vDis(m_c, vectorint(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 100000;int m_c, m_iMaskCount;};2023年1月
class Solution { public: int shortestPathLength(vectorvector 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; } vectorstd::pairint,int m_vQue; int m_vMaskPosMinOpe[1 12 ][12]; int m_c; };
2023年8月
class Solution { public: int shortestPathLength(vectorvector 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; } vectorstd::pairint,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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
