图论 Dijstra Floyd Bellman-Ford

最短路 Dijstra算法求单元最短路

—— 定点到每个点的最短路时间复杂度O(n^2)

核心思路：

每次从「未求出最短路径的点中取出距离起点最近的点，以这个点为桥梁刷新「未求出最短路径的点」的距离

最短路 - 题目 - Daimayuan Online Judge

#include
using namespace std;

#define V vector
#define pii pair
using ll = long long;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int N =5e3 + 5;

struct node
{
	int v, dis;
};
int n, m, k;
int dis[N];
Vh[N];

void dij(int s, int e)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
  //优先队列优化时间 也可用set函数达成相同效果
	priority_queue, greater >q;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		pii it = q.top(); q.pop();
		int u = it.second;
		for (int i = 0; i < h[u].size(); i++)
		{
			node tmp = h[u][i];
           //如果更新了一个节点，则放入队列中
			if (dis[tmp.v] > dis[u] + tmp.dis)
			{
				dis[tmp.v] = dis[u] + tmp.dis;
				q.push({ dis[tmp.v],tmp.v });
			}
		}
	}
	if (dis[e] == 0x3f3f3f3f)
		cout << -1;
	else cout << dis[e];
	cout << endl;
}
void add(int u, int v, int dis)
{
	h[u].push_back({ v, dis });
}
int main()
{
	cin >> n >> m >> k;
	while (m--)
	{
		int v, u, dis;
		cin >> u >> v >> dis;
		add(u, v, dis);
	}
	while (k--)
	{
		int u, v; cin >> u >> v;
		dij(u, v);
	}
}

ps小技巧:

Dijstra仍可以用来在有向图中找寻每个点到定点最短距离

（反建有向图，仍进行一遍以起点s 的Dijstra，那么s能到的点e，即为e出发能到s的最短路）

聚会 - 题目 - Daimayuan Online Judge

标题

#include
using namespace std;

#define V vector
#define pii pair
using ll = long long;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int N = 1e5 + 5;

struct node
{
	int v, dis;
};
int n, m, k;
int dis[N];
Vh1[N],h2[N];
int t1[N];
//优化代码 多加一个*h
void dij(V*h,int s)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	priority_queue, greater >q;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		pii it = q.top(); q.pop();
		int u = it.second;
		for (int i = 0; i < h[u].size(); i++)
		{
			node tmp = h[u][i];
			if (dis[tmp.v] > dis[u] + tmp.dis)
			{
				dis[tmp.v] = dis[u] + tmp.dis;
				q.push({ dis[tmp.v],tmp.v });
			}
		}
	}
}
void add(V*h, int u, int v, int dis)
{
	h[u].push_back({ v, dis });
}
int main()
{
	cin >> n >> m >> k;
	while (m--)
	{
		int v, u, dis;
		cin >> u >> v >> dis;
		add(h1,u, v, dis);
        //!!!!!
		//反向存图，求每个点到起点最短距离
		add(h2,v, u, dis);
	}
	dij(h1,k);
	memcpy(t1, dis, sizeof(dis));
	dij(h2, k);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, 1LL*t1[i] + dis[i]);
	cout << ans << endl;
}

最短路Floyd算法时间复杂度O(n^3)

——处理任意两个点的最短路

最短路3 - 题目 - Daimayuan Online Judge

核心代码：

在 i->j的路径中可能中间经过0-n-2个点来达成最短路

dp[k][i][j]记录从 i->j 经过 1--k 中某些点（可为0）达成的最短路径

和区间dp有相似思维

for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				//判断有无边链接，预防爆int
				if (dp[i][k] < 1 << 30 && dp[k][j] < 1 << 30)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

code:

#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;

#define V vector
#define pii pair
using ll = long long;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int N = 1e5 + 5;


//Floyd算法 核心思想为dp  时间复杂度 O(n^3) 
// !!!复杂度只和节点数量有关
//转化方程  dp[k][i][j]=min(dp[k-1][i][k]+dp[k-1][k][j],dp[k-1][i][j])
int dp[301][301];
//为dp[301][301][301]的空间优化

int n, m, q;
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	//设置为∞ 表示没有边相连
	memset(dp, 127, sizeof(dp));
	//到自己的路径为0
	for (int i = 1; i <= n; i++)
		dp[i][i] = 0;
	for (int i = 1; i <= m; i++)
	{
		int u, v,z;
		scanf("%d%d%d", &u, &v,&z);
      //此时表示 u->v不经过任何点的距离
		dp[u][v] = z;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				//判断有无边链接，预防爆int
				if (dp[i][k] < 1 << 30 && dp[k][j] < 1 << 30)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	//O(1)查询
	//!!!使用 printf scanf 防止超时
	while (q--)
	{
		int s, e; 
		scanf("%d%d", &s, &e);
		if (dp[s][e] < 1 << 30)
			printf("%d", dp[s][e]);
		else printf("-1");
		printf("n");
	}
}

深入理解：

删点游戏 - 题目 - Daimayuan Online Judge

该题目中，每次删去一个点后询问都要使用一次Floyd 时间复杂度O(n^4)----n*O(Floyd)

可以逆向思维，在每加入一点的时候用Floyd更新一次

//在此题中，就可更深层次理解Floyd算法实质就相当于不断加入一个中间桥梁k，来更新dp[i][j]

#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;

#define V vector
#define pii pair
using ll = long long;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int N = 1e5 + 5;

int n, c[301], dp[301][301];
bool vis[301];
int a[301];
int main()
{
	scanf("%d", &n);
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &dp[i][j]);
		}
	for (int i = 1; i <= n; i++)
	{
		 scanf("%d", &c[i]);
	}
	memset(vis, false, sizeof(vis));
   //逆向遍历，相当于加入一个点
	for (int l = n; l; l--)
	{
		int k = c[l];
		vis[k] = 1;
		for(int i=1;i<=n;i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
		int ans = 0;
		for(int i=1;i<=n;i++)
			for (int j = 1; j <= n; j++)
				if (vis[i] && vis[j])
					ans += dp[i][j];
		a[l] = ans;
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", a[i]);
	}
}

最短路 Bellman-Ford算法时间O（n*m）

用处：证明负环

int dis[maxn];
struct edge{
    int s,e;    ///起点，终点
    int w;      ///权值
}e[maxn];
int n,m;                //n为点,m为边的总数
bool bellman(int a,int n)     ///求a->其他点的最短路,n为结点总数.可判负环
{
    memset(dis,inf,(n+1)<<2);    //将数组前n+1个数初始化为INF      
    dis[a]=0;
    For(i,n-1) ///for(int i=0;iv和u->k->v
    For(i,m)                                                    ///松弛完后还能再松弛即代表有负环
        if(dis[e[i].e]>dis[e[i].s]+e[i].w)
            return true;
    return false;

————————————————
版权声明：本文为CSDN博主「bestsort」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/bestsort/article/details/80100039

图论 Dijstra Floyd Bellman-Ford

C/C++/C#相关栏目本月热门文章