图论最短路(floyed+ford)

发布于:2024-11-28 ⋅ 阅读:(17) ⋅ 点赞:(0)

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;
}