美食美客网站建设项目规划书,国内最新新闻,地方农产品网站建设,评论插件 wordpress最短路径算法对图结构没有特殊要求#xff0c;不要求连通图#xff0c;且有向图无向图均可。
最短路径算法目标是求得从某顶点出发#xff0c;沿图的边到达另一顶点所经过的路径中#xff0c;各边上权值之和最小的一条路径。解决最短路的问题有以下算法#xff1a;Dijkst…最短路径算法对图结构没有特殊要求不要求连通图且有向图无向图均可。
最短路径算法目标是求得从某顶点出发沿图的边到达另一顶点所经过的路径中各边上权值之和最小的一条路径。解决最短路的问题有以下算法Dijkstra算法Floyd算法和SPFA算法等。其中SPFA算法可以处理边权值为负数图结构。而最为好用的是使用堆优化的Dijstra算法。 一Dijkstra算法
算法采用动态规划的思想通过对图结构的递推得到从点X出发到其他所有结点的最短路径不能处理边权为负值情况。以下图为例求结点1出发到其余各结点最短路径。
1先找到从1出发的邻接点有234最短的边是13长度5此时可以断言结点1到结点3最短路径是5。证明也很容易因为其他路径必须先经过12长度10或者14长度9那么其长度必然大于5。
2从3出发找寻到其他结点更短的路径可以发现
532长度2要比原来的12长度10更小进行数据的更新
535长度6就不如原有的14长度9不作更新操作
535长度1要比原来的15长度无穷大更小进行数据的更新。
更新全部之后选出最小的路径此时为132长度7此路径为结点1到结点2的最短路径。然后从结点2出发继续找寻到其他结点更短的路径。 算法实现细节1用v数组标记已经求出最短路径的结点2用d数组记录最短路径长度通过迭代方式更新d数组找到当前最短路径结点。
邻接表存储的算法实现。
#include bits/stdc.h
typedef long long ll;
using namespace std;
int n,m,v[105],d[105];
struct node
{int adj,val;
};
vectornodee[105];
int getMin()
{int mini0,i;for(i1;in;i)if(v[i]0d[i]d[mini])minii;return mini;
}
void djstra(int s)
{int i,j;memset(d,127/3,sizeof(d));/** 初始化d数组 */d[s]0;/** s为起点 */for(i1; in; i){int tempgetMin();v[temp]1;for(j0; je[temp].size(); j) /** e[1] 存的是2 4 5e[1][j] */{int xe[temp][j].adj,ze[temp][j].val;if(v[x]0d[x]d[temp]z)d[x]d[temp]z;}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y,z,ans0;cinnm;for(i1; im; i){cinxyz;e[x].push_back({y,z});e[y].push_back({x,z});}djstra(1);if(d[n]1e8)coutd[n];elsecout-1;return 0;
}邻接表用堆优化的算法
#include iostream
#includecstring
#include queue
#includevector
typedef long long ll;
using namespace std;
int n,m,v[105],d[105];
struct node
{int adj,val;bool operator(const node B)const/** 重载操作符用于优先队列排序 */{return valB.val;}
};
vectornodee[105];
priority_queuenodepq;
int getMin()/** 用堆之后查找复杂度降为log级别 */
{while(pq.size()v[pq.top().adj])/** 存在堆顶元素已经访问的情况 */pq.pop();int vpq.top().adj;pq.pop();return v;
}
void djstra(int s)
{int i,j;memset(d,127/3,sizeof(d));/** 初始化d数组 */d[s]0;/** s为起点 */for(i1; in; i)/** 初始化优先队列放入结点i和对应的d[i],这里只是借用node类型这两个值可不是邻接点和权值正常来说需要再定义一个结构体类型 */pq.push({i,d[i]});for(i1; in; i){int tempgetMin();v[temp]1;for(j0; je[temp].size(); j) /** e[1] 存的是2 4 5e[1][j] */{int xe[temp][j].adj,ze[temp][j].val;if(v[x]0d[x]d[temp]z)d[x]d[temp]z,pq.push({x,d[x]});}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y,z,ans0;cinnm;for(i1; im; i){cinxyz;e[x].push_back({y,z});e[y].push_back({x,z});}djstra(1);if(d[n]1e8)coutd[n];elsecout-1;return 0;
}二Floyd算法
必须使用邻接矩阵存储结构。基于动态规划思想通过n个点的拉伸得到任意两点最短路径。检查每一个结点k试探能否通过k为中间结点减少结点i和j的最短路径长度。Floyd算法时间复杂度较高On3但是能用于求任意两点最短路径。算法简单只适用于结点数较少的情况。
#include iostream
#include cstring
typedef long long ll;
using namespace std;
int n,m,a[105][105];
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,k,x,y,z;cinnm;memset(a,127/3,sizeof(a));for(i1;im;i){cinxyz;/** 必须无向图 */a[x][y]a[y][x]z;}for(k1;kn;k){for(i1;in;i){for(j1;jn;j){if(a[i][j]a[i][k]a[k][j])/** 检查以k为中间点是否能减少i和j的路径长度 */a[i][j]a[i][k]a[k][j];}}}if(a[1][n]9999999)cout-1;elsecouta[1][n];return 0;
}三SPFA算法
SPFA算法写起来和BFS算法几乎一模一样也被称为队列优化算法通常用于求含负权边的单源最短路径以及判负权环。其处理过程和迪杰斯特拉区别在于迪杰斯特拉算法需要找到最小的那个结点而SPFA不管那些只要一个结点的当前路径长度低于之前已有的值那么就送入队列因为新的路径长度可能刷新其他结点的最短路径长度。
#include iostream
#include string.h
#includevector
#includequeue
typedef long long ll;
using namespace std;
int n,m,v[100005],d[100005];/** V表示结点是否在队列中 */
vector pairint,int e[100005];
void spfa(int x)
{int i,temp;d[x]0;queueintq;q.push(x);/** 起点入队 */while(!q.empty()){tempq.front();/** temp出队结点如果一个结点会反复入队出队超过n次那么有负环存在 */q.pop();v[temp]0;/** 修改标志未来可能会再次入队 */for(i0;ie[temp].size();i){int ye[temp][i].first,ze[temp][i].second;if(d[y]d[temp]z) /** y结点的路径长度变短 */{d[y]d[temp]z;if(v[y]0)/** 如果y结点此时不在队列中加入队列中 */{q.push(y);v[y]1;/** 标记一下假如在y出来之前又一次d[y]d[temp]z那么也不用重复入队 */}}}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y,z,s;cinnm;for(i1;im;i){cinxyz;if(xy)continue;e[x].push_back({y,z});e[y].push_back({x,z});}memset(d,127,sizeof(d));spfa(1);cout(d[n]9999999?-1:d[n]);return 0;
}
