竖排导航网站,58同城怎么发布信息,个人博客内容,做钢材销售客户哪里去开发网站一.最短路径的介绍 最短路径是图论和网络分析中一个重要的概念#xff0c;它指的是在一个图或网络中连接两个节点或顶点的路径中#xff0c;具有最小权重总和的路径。这个权重可以表示为路径上边或弧的长度、耗费、时间等#xff0c;具体取决于问题的背景和应用场景。 如果你…一.最短路径的介绍 最短路径是图论和网络分析中一个重要的概念它指的是在一个图或网络中连接两个节点或顶点的路径中具有最小权重总和的路径。这个权重可以表示为路径上边或弧的长度、耗费、时间等具体取决于问题的背景和应用场景。 如果你有学过最小生成树你会发现二者是有部分相同点的都是在找权重和的最小值。
但是最小生成树找的是沟通所有节点的最小权重而最短路径是找的是一个节点到另一个节点的最小权重。
因为从一个节点到另一个节点往往有多种路径路径的长短也不同我们的目的就是为了找到一个最短的路径来达到省时省力的目的。 比如我们从A节点到E节点分别有三条路径。 上路径2A-B4B-E6 中路径10A-E 下路径4A-C2C-D6D-E12 那么我们怎么使用代码找出最短路径呢
用于解决最短路径可以使用Dijkstra 算法、SPFA算法、Floyd 算法等。
下面我们对这几种算法来介绍一下。
二.算法介绍
这里先给出一个例题使用下面介绍成所有算法解决。
例题 输入数据
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 41.Dijkstra 算法 Dijkstra 算法基于贪心策略通过逐步找到从起点到所有其他节点的最短路径来工作。它适用于权重为非负的有向图和无向图。 算法的实现有以下几个步骤 1.distances距离数组用于存储从起点到每个节点的最短距离估计值。初始时将起点到自身的距离设置为0其他节点的距离设置为无穷大。 2.visited标记数组用于标记节点是否已经被访问过。初始时将所有节点标记为未访问。 3.previous前驱数组用于记录到达每个节点的最短路径中当前节点的前一个节点是哪个。 4.从起点开始将起点标记为当前节点更新起点到相邻节点的距离并将这些相邻节点加入候选集。 5.从候选集中选择距离最短的节点作为当前节点并将其标记为已访问。 6.对于当前节点的每个相邻节点如果经过当前节点到达该相邻节点的路径比起始点直接到达该节点的路径更短则更新距离数组和前驱数组。 7.重复步骤3和步骤4直到所有节点都被访问过或候选集为空。 8.最终得到起点到每个节点的最短路径长度和最短路径。 下面是实现例题的完整代码含注释
#includebits/stdc.h
#define M 500010
#define inf 1234567890
using namespace std;
struct edge{int u,v,w,next;
}e[M];
struct node{int w,now;bool operator(const node k)const{return wk.w;//堆优化小的元素放在堆顶大根堆 }
};
int head[M],re0,n,m,s,v[M],dis[M];
priority_queuenodeq;
void add(int u,int v,int w)//链式前向星存图
{e[re].uu;e[re].vv;e[re].ww;e[re].nexthead[u];head[u]re;
}
void dijkstra()
{for(int i1;in;i) dis[i]inf;//将点设置为无穷大 dis[s]0;//起点设置为0 node p;p.w0,p.nows;q.push(p);while(!q.empty()){node kq.top();q.pop();int uk.now;if(v[u]) continue;//如果遍历过直接跳过循环 v[u]1;for(int ihead[u];i;ie[i].next){//下一个点 int ve[i].v;if(dis[v]dis[u]e[i].w)//更新最小权重 {dis[v]dis[u]e[i].w;q.push((node){dis[v],v});} }}
}
int main()
{cinnms;for(int i0;im;i){int u,v,w;cinuvw;//建边 add(u,v,w);}dijkstra();for(int i1;in;i){coutdis[i] ;}return 0;
}
我们来看运行结果 也是成功AC。
2.SPFA算法 SPFA算法是一种用于解决单源最短路径问题的算法是 Bellman-Ford 算法的一种优化版本。它通过队列实现松弛操作以减少不必要的松弛次数从而提高了算法的效率。 算法实现步骤 1.distances距离数组用于存储从起点到每个节点的最短距离估计值。初始时将起点到自身的距离设置为0其他节点的距离设置为无穷大。 2.queue队列用于存储待处理的节点。初始时将起点加入队列。 3.in_queue标记数组用于标记节点是否已经在队列中。初始时将起点标记为在队列中。 4.从队列中取出一个节点作为当前节点遍历该节点的所有相邻节点。 5.对于每个相邻节点如果经过当前节点到达该相邻节点的路径比起始点直接到达该节点的路径更短则更新距离数组并将该相邻节点加入队列。 6.重复直到队列为空。 下面是实现例题的完整代码
#includebits/stdc.h
#define M 500010
#define inf 1234567890
using namespace std;
struct edge{int u,v,w,next;
}e[M];
int head[M],re0,n,m,s,v[M],dis[M];
void add(int u,int v,int w)//链式前向星存图
{e[re].uu;e[re].vv;e[re].ww;e[re].nexthead[u];head[u]re;
}
queueintq;//队列优化
void SPFA()
{for(int i1;in;i) dis[i]inf;//将点设置为无穷大 dis[s]0;//起点设置为0 q.push(s);while(!q.empty()){//直到所有节点全部入队不会再有新的节点入队慢慢出队至停止循环 int kq.front();q.pop();v[k]0;for(int ihead[k];i;ie[i].next){//下一个点 int pe[i].v;if(dis[p]dis[k]e[i].w)//更新最小权重 {dis[p]dis[k]e[i].w;if(!v[p])//如果不在队列里面则入队 {v[p]1;q.push(p);}} }}
}
int main()
{cinnms;for(int i0;im;i){int u,v,w;cinuvw;//建边 add(u,v,w);}SPFA();for(int i1;in;i){coutdis[i] ;}return 0;
}
下面是运行结果 虽然运行结果正确但是SPFA算法容易被卡数据导致时间超限。 3.Floyd 算法 Floyd算法的时间复杂度为O(N^3)其中N是节点的数量。因此对于大型图Floyd算法可能会变得相对缓慢。然而与其他单源最短路径算法不同Floyd算法可以同时计算任意两个节点之间的最短路径这在某些情况下可能是更方便的。 Floyd算法的核心是下面这个方程式来自动态规划。 dp[j][k]min(dp[j][k],dp[j][i]dp[i][k]); 算法实现步骤 初始化距离矩阵将矩阵D初始化为图的邻接矩阵如果两个节点之间有直接的边则距离为边的权重否则距离为无穷大。同时将对角线上的元素即节点到自身的距离初始化为0。 三重循环对于每一对节点ij作为可能的中间节点k检查是否存在路径从节点i到节点j通过节点k的路径比直接从i到j的路径更短。如果是则更新路径长度。 返回最终的距离矩阵D其中D[i][j]表示从节点i到节点j的最短路径长度。 Floyd算法是这三种算法中最简单的核心代码只有一点。
for(int i1;in;i){for(int j1;jn;j){if(ij||dp[j][i]inf) continue;for(int k1;kn;k){dp[j][k]min(dp[j][k],dp[j][i]dp[i][k]);} }}
下面是完整代码
#includebits/stdc.h
using namespace std;
#define M 10010
#define inf 1234567890
int n,m,s,dp[M][M];
void floyd()
{for(int i1;in;i){for(int j1;jn;j){if(ij||dp[j][i]inf) continue;//找存在边 for(int k1;kn;k){dp[j][k]min(dp[j][k],dp[j][i]dp[i][k]);//更新最小权重 } }}
}
int main()
{cinnms;for(int i1;in;i)for(int j1;jn;j)dp[i][j]inf;//初始化矩阵 for(int i1;im;i){int u,v,w;cinuvw;dp[u][v]min(dp[u][v],w);//防止重边 }dp[s][s]0;floyd();for(int i1;in;i){coutdp[s][i] ;}return 0;
}
下面是运行结果 结果虽然正确但是对于这题来说运行速度太慢了。 所以在做题时需要按照题目要求来选择合适算法。
三.总结 Dijkstra算法 简介 Dijkstra算法是解决单源最短路径问题的一种贪心算法。它从起点开始逐步找到从起点到所有其他节点的最短路径。运行速度 在最坏情况下Dijkstra算法的时间复杂度为O((VE)logV)其中V是节点数E是边数。在使用最小堆的实现中它通常具有较好的性能。 SPFA算法 简介 SPFA算法是Bellman-Ford算法的一种优化版本通过使用队列来避免不必要的重复松弛操作提高了效率。运行速度 SPFA算法的平均时间复杂度通常被认为是O(kE)其中k是一个常数。在实际应用中它的性能通常比Bellman-Ford算法好但对于存在负权回路的图SPFA算法可能陷入死循环。 Floyd算法 简介 Floyd算法是一种动态规划算法用于解决图中所有节点对之间的最短路径问题。它通过迭代更新每一对节点之间的最短路径长度。运行速度 Floyd算法的时间复杂度为O(N^3)其中N是节点的数量。在大型图上可能变得相对缓慢但与其他单源最短路径算法不同Floyd算法可以同时计算任意两个节点之间的最短路径。
速度比较 Dijkstra算法通常在稠密图上表现良好特别是当使用最小堆等数据结构进行优化时。Floyd算法的运行速度可能在大型图上较慢但由于同时计算所有节点对之间的最短路径它在某些情况下可能更方便。 总体而言选择算法通常取决于图的规模、稀密度、边权重分布以及是否需要同时计算所有节点对之间的最短路径。 本篇完~
