图的五种最短路径算法

2024-07-09 18:56| 来源: 网络整理| 查看: 265

本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，费罗伊德算法，迪杰斯特拉算法，Bellman-Ford 算法。

1）深度或广度优先搜索算法（解决单源最短路径）

从起点开始访问所有深度遍历路径或广度优先路径，则到达终点节点的路径有多条，取其中路径权值最短的一条则为最短路径。

下面是核心代码：

void dfs(int cur,int dst){ if(minpathdst){ minpath=dst; return; } } for( int i= 1;in>>m&&n!= 0){ //初始化邻接矩阵 for( int i= 1;ia>>b; cin>>edge[a][b]; } minpath=inf; memset(mark, 0, sizeof(mark)); mark[ 1]= 1; en=n; dfs( 1, 0); coutedge[a][b]; edge[b][a]=edge[a][b]; } for( int k= 1;k int to,val,next; }e[ 200100]; int head[ 200100],vis[ 200100],dis[ 200100]; void add(int from,int to,int val){ e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len; len++; } void spfa() { queue< int>q; q.push( 1); vis[ 1]= 1; while(!q.empty()) { int t=q.front(); q.pop(); vis[t]= 0; for( int i=head[t];i!= -1;i=e[i].next){ int s=e[i].to; if(dis[s]>dis[t]+e[i].val){ dis[s]=dis[t]+e[i].val; if(vis[s]== 0){ q.push(s); vis[s]= 1; } } } } } int main(){ int from,to,val; while( cin>>n>>m){ memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); /* for(int i=1;i

【本文地址】

公司简介

联系我们