图论·最短路径问题

文章目录最短路径问题的定义搜索单源和多源搜索问题单源最短路径Dijsktra算法例题朴素实现O ( n 2 ) O(n^2)O(n2)堆优化版本O ( m l o g n ) O(mlogn)O(mlogn)时间复杂度分析链表前向星STL链表实现失效情况边权值为负数Bellman_ford算法用法负权重图的最短路问题 和 负环路例题朴素实现O ( n m ) O(nm)O(nm)SPFAO ( m ) − O ( n m ) O(m)-O(nm)O(m)−O(nm)最短路径问题的定义搜索单源和多源搜索中的最短路单源最短路问题多源最短路问题搜索问题参考图论·搜索最短路径BFS权值为1情况下的最短路径A*权值不为1的情况下的最短路径启发式算法单源最短路径参考图论·单源最短路径·Bellman_ford算法Dijsktra算法三部曲贪心选点加入集合更新距离例题849. Dijkstra求最短路 I850. Dijkstra求最短路 II朴素实现O ( n 2 ) O(n^2)O(n2)intn,m,g[509][509],visited[509],dist[509];intdj(){dist[1]0;for(inti1;in;i){intidx-1,tempMAX_VALUE;for(intj1;jn;j){if(!visited[j]dist[j]temp){tempdist[j];idxj;}}if(idx-1)break;visited[idx]1;for(intj1;jn;j){if(!visited[j]g[idx][j]!MAX_VALUE){dist[j]min(dist[j],dist[idx]g[idx][j]);}}}returndist[n]MAX_VALUE?-1:dist[n];}堆优化版本O ( m l o g n ) O(mlogn)O(mlogn)朴素实现的问题每次都需要手动遍历寻找dist[i]最小的节点加入数组每一次都要遍历邻接矩阵中所有终点的边(存在无效遍历)。使用堆来获得dist[i]的数组使用邻接表来优化邻接矩阵的存储(减少无效边的遍历)。堆中存储当前加入节点和离起点的距离。时间复杂度分析时间复杂度分析更新邻接矩阵所有边时间复杂度为O ( m ) O(m)O(m)然后不需要遍历所有节点通过堆来加入节点堆中元素至多为m个(将所有相邻边的节点加入)因此取出和插入操作复杂度为O ( l o g m ) O ( l o g n ) O(logm)O(logn)O(logm)O(logn)因此总共复杂度为O ( m l o g n ) O(mlogn)O(mlogn)链表前向星额外定义w数组w[i]表示存储与i位置的节点(存储于i ! 节点i)的边权值。intn,m;inth[150009],node[150009],w[150009],nxt[150009],len0,dist[150009],visited[150009];classcmp{public:booloperator()(constpairint,inta,constpairint,intb){returna.secondb.second;}};priority_queuepairint,int,vectorpairint,int,cmpq;voidinsert(intx,inty,intz){len;node[len]y;w[len]z;nxt[len]h[x];h[x]len;}intdj(){dist[1]0;q.push(make_pair(1,0));while(q.size()){pairint,intcurq.top();q.pop();if(visited[cur.first])continue;visited[cur.first]1;for(intih[cur.first];i!-1;inxt[i]){intvnode[i];// nodes numberintweightw[i];if(!visited[v]dist[cur.first]weightdist[v]){dist[v]dist[cur.first]weight;q.push(make_pair(v,dist[v]));}}}returndist[n]MAX_VALUE?-1:dist[n];}STL链表实现intn,m;vectorlistpairint,intg(1500009);vectorintvisited(1500009,0);vectorintdist(1500009,MAX_VALUE);classcmp{public:booloperator()(constpairint,inta,constpairint,intb){returna.secondb.second;//small top heap}};priority_queuepairint,int,vectorpairint,int,cmpq;intdj(){dist[1]0;q.push({1,0});// node, distwhile(q.size()){autocurq.top();q.pop();if(visited[cur.first]){continue;}visited[cur.first]1;for(autoitem:g[cur.first]){if(!visited[item.first]dist[cur.first]item.seconddist[item.first]){dist[item.first]dist[cur.first]item.second;q.push({item.first,dist[item.first]});}}}returndist[n]MAX_VALUE?-1:dist[n];}失效情况边权值为负数简要证明思路和理解如下贪心假设加入到当前集合中的节点都是离起点的距离最短。情况分析假设有一个边的权值为负数但是它还没有被加入到当前集合中(例如离当前集合中所有点在图上的距离相对较远)。失效案例假设该边的权值为-无穷加入到当前集合中可以使得当前集合中所有点到出发点的距离更新为负无穷贪心假设不成立(这说明当前集合中所有点到出发点的距离不一定最短)矛盾Bellman_ford算法参考图论·单源最短路径·Bellman_ford算法松弛操作dist[j]dist[i]graph[i][j]相当于动态规划dist[j]的距离减少但是到dist[j]的路径长度增加1引入中间节点减少距离。用法负权重图的最短路问题 和 负环路可以用于负权重图的单源最短路可以用于检测是否存在负环路如果第n1次更新有效的话那么图中一定存在负环路。例题853. 有边数限制的最短路有边数限制的含负权重图只能使用BF算法朴素实现O ( n m ) O(nm)O(nm)遍历每一个边进行松弛即可为了控制最短距离中路径的长度需要定义一个二维数组确保使用的是之前的数据。注意dist[i][j]表示起点1到点i长度j的路径所需要的最短距离。intn,m,k;typedefstructnode{intx,y,z;};node edges[10009];intdist[509][509];voidbf(){for(inti0;ik;i)dist[1][i]0;for(inti1;ik;i){for(intj1;jm;j){intxedges[j].x,yedges[j].y,zedges[j].z;// 避免路径长度超过限制:例如 i1时, x,y y,z 按顺序加入, 此时dist[z]的长度最短,但是不符合dp数组的定义(路径长度超过1).dist[y][i]min(dist[y][i],dist[x][i-1]z);}}if(dist[n][k](MAX_VALUE/2))coutimpossible;elsecoutdist[n][k];}voidsolve(){cinnmk;memset(dist,0x3F,sizeofdist);for(inti1;im;i){inta,b,c;cinabc;edges[i]{a,b,c};}bf();}SPFAO ( m ) − O ( n m ) O(m)-O(nm)O(m)−O(nm)优化思路动态规划的更新方法中存在一些无效操作例如如果dist[x][i-1]在第i-1轮中没有更新那么这一步更新操作可以省略。我们可以只记录更新过后的节点将其加入到队列中确保所有的更新操作都是高效的。注意这里的节点可以重复加入。intn,m;vectorlistpairint,intg(100009);// node, weightqueueintq;intvisited[100009],dist[100009];voidspfa(){dist[1]0;q.push(1);while(q.size()){intcurq.front();q.pop();// 允许重复更新visited[cur]0;for(autoitem:g[cur]){if(dist[cur]item.seconddist[item.first]){dist[item.first]dist[cur]item.second;// 确保不存在多个重复的结点数if(!visited[item.first]){q.push(item.first);}}}}if(dist[n](MAX_VALUE/2)){coutimpossible;}elsecoutdist[n];}