图论最短路(floyed+ford)

Floyd 算法简介

Floyd 算法（也称为 Floyd-Warshall 算法）是一种动态规划算法，用于解决所有节点对之间的最短路径问题。它可以同时处理加权有向图和无向图，包括存在负权边的情况（只要没有负权环）。

核心思想

Floyd 算法的基本思想是利用动态规划，通过逐步引入中间节点优化路径，最终得到每对节点之间的最短路径。

假设图的节点编号为 1,2,…,n，dist[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 的路径更短，如果更短，则更新。

算法流程

1. 初始化距离矩阵 dist：

   • 如果 i=j，dist[i][j] = 0（自身到自身的距离为 0）。
   • 如果 i≠j 且存在边 (i,j)，dist[i][j] = data(边的权值)。
   • 如果 i≠j 且不存在边 (i,j)，dist[i][j] = INT_MAX（表示无穷大，路径不存在）。

2. 动态规划：

   • 依次引入节点 k（k=1,2,…,n）作为中间节点，更新所有节点对之间的最短路径。
   • 按公式更新 dist[i][j]。

3. 检查结果：

   • 遍历 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;cin>>n>>m;cout<<"输入a点到b点的距离"<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=100000;}}for(int i=1;i<=m;i++){cin>>a>>b;cin>>dis[a][b];dis[b][a]=dis[a][b];}cout<<"输入想查找的两个点的编号"<<endl; cin>>want1>>want2;for(int k=1;k<=n;++k){for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(dis[i][j]>dis[i][k]+dis[k][j]){dis[i][j]=dis[i][k]+dis[k][j];  }}}}cout<<want1<<"->"<<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 为节点数），确保找到从源点到所有节点的最短路径（若无负权环）。

---

算法流程

1. 初始化：

   • 将源点的距离设为 0（dist[src] = 0）。
   • 其他节点的初始距离设为无穷大（dist[i] = \infty）。

2. 松弛所有边：

   • 重复 n−1 次（最多需要 n−1 次遍历，因为最短路径最多包含 n−1 条边）。
   • 对图中每条边 (u,v,w)，尝试更新节点 vvv 的距离。

3. 检查负权环：

   • 再次遍历所有边。如果发现还能继续松弛，说明存在负权环。

代码

#include <bits/stdc++.h>
using namespace std;
int d[110],n,m,s=1,k;
struct Theedge
{int start,end,data;
}edge[110];
int main()
{cin>>n>>m>>s>>k;for(int i=1;i<=m;i++){cin>>edge[i].start>>edge[i].end>>edge[i].data;}for(int i=1;i<=n;i++){d[i]=100000;}d[s]=0;for(int i=1;i<=n-1;i++){for(int j=1;j<=m;j++){int x=edge[j].start;int y=edge[j].end;int z=edge[j].data;d[y]=min(d[y],d[x]+z);d[x]=min(d[x],d[y]+z);}}cout<<d[k];return 0;
}