图论最短路(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;
}