备案个人网站 淘宝客,网站策划方案书的内容,网站首页图,个人缴纳养老保险Floyd 算法简介
Floyd 算法#xff08;也称为 Floyd-Warshall 算法#xff09;是一种动态规划算法#xff0c;用于解决所有节点对之间的最短路径问题。它可以同时处理加权有向图和无向图#xff0c;包括存在负权边的情况#xff08;只要没有负权环#xff09;。
核心思…Floyd 算法简介
Floyd 算法也称为 Floyd-Warshall 算法是一种动态规划算法用于解决所有节点对之间的最短路径问题。它可以同时处理加权有向图和无向图包括存在负权边的情况只要没有负权环。
核心思想
Floyd 算法的基本思想是利用动态规划通过逐步引入中间节点优化路径最终得到每对节点之间的最短路径。
假设图的节点编号为 1,2,…,ndist[i][j] 表示节点 i 到节点 j 的当前最短路径长度算法通过以下递推公式更新 dist[i][j]
dist[i][j]min(dist[i][j],dist[i][k]dist[k][j])
其中
i起点j终点k中间节点
含义判断是否通过节点 k 可以使 i 到 j 的路径更短如果更短则更新。
算法流程 初始化距离矩阵 dist 如果 ijdist[i][j] 0自身到自身的距离为 0。如果 i≠j 且存在边 (i,j)dist[i][j] data(边的权值)。如果 i≠j 且不存在边 (i,j)dist[i][j] INT_MAX表示无穷大路径不存在。 动态规划 依次引入节点 kk1,2,…,n作为中间节点更新所有节点对之间的最短路径。按公式更新 dist[i][j]。 检查结果 遍历 dist 矩阵获得任意两点之间的最短路径。如果对角线上的 dist[i][i] 0说明存在负权环。
代码
#include bits/stdc.h
using namespace std;
int dis[110][110],n,m,a,b,want1,want2;
int main()
{cout请输入点数,边数endl;cinnm;cout输入a点到b点的距离endl;for(int i1;in;i){for(int j1;jn;j){dis[i][j]100000;}}for(int i1;im;i){cinab;cindis[a][b];dis[b][a]dis[a][b];}cout输入想查找的两个点的编号endl; cinwant1want2;for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(dis[i][j]dis[i][k]dis[k][j]){dis[i][j]dis[i][k]dis[k][j]; }}}}coutwant1-want2最短的距离为dis[want1][want2];return 0;
}
Ford 算法简介
Ford 算法通常指 Bellman-Ford 算法是一种用于计算单源最短路径的经典算法。它可以在加权有向图中找到从一个源点到所有其他节点的最短路径支持负权边并且能够检测负权环。 算法思想
Bellman-Ford 算法的核心思想是通过松弛操作Relaxation逐步更新最短路径估计值。它基于以下性质
如果存在从节点 u 到节点 v 的边 (u,v,w)并且通过这条边可以缩短路径那么更新路径长度 dist[v]min(dist[v],dist[u]w)
算法执行 n−1 次松弛操作n 为节点数确保找到从源点到所有节点的最短路径若无负权环。 算法流程 初始化 将源点的距离设为 0dist[src] 0。其他节点的初始距离设为无穷大dist[i] \infty。 松弛所有边 重复 n−1 次最多需要 n−1 次遍历因为最短路径最多包含 n−1 条边。对图中每条边 (u,v,w)尝试更新节点 vvv 的距离。 检查负权环 再次遍历所有边。如果发现还能继续松弛说明存在负权环。
代码
#include bits/stdc.h
using namespace std;
int d[110],n,m,s1,k;
struct Theedge
{int start,end,data;
}edge[110];
int main()
{cinnmsk;for(int i1;im;i){cinedge[i].startedge[i].endedge[i].data;}for(int i1;in;i){d[i]100000;}d[s]0;for(int i1;in-1;i){for(int j1;jm;j){int xedge[j].start;int yedge[j].end;int zedge[j].data;d[y]min(d[y],d[x]z);d[x]min(d[x],d[y]z);}}coutd[k];return 0;
}
