一个自己捣鼓出来的最短路径算法,有若干问题,欢迎各路神仙来看看
  • 板块学术版
  • 楼主五年长久
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/4/1 21:35
  • 上次更新2023/10/23 19:43:11
查看原帖
一个自己捣鼓出来的最短路径算法,有若干问题,欢迎各路神仙来看看
444078
五年长久楼主2023/4/1 21:35

我自己基于BFS造出了一个类似SPFA的最短路径算法,完全是搞着玩的,大伙不要在意,但是我有几个问题希望各位求教:

  1. 这个算法就是SPFA吗?如果是,请说明相同点,如果不是,请帮忙算算它的时间复杂度并提出优化方式(注意,我是从BFS中推演出来的);
  2. 这个代码可以被说明是正确的吗?如果可以,请简单说明,如果不可以,请提出反例(我在一个Dijkstra的题目上已经提交满分了);
  3. 这个代码是否其实是某种已知算法的儿子,或者就是畸形种?能否说明?

下面是我的代码。

//exam name:A New Shortest Path Way
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
	int next,w;
};
const int MAXN=10005;
const int INF=0x3f3f3f3f;
vector<edge> g[MAXN];
queue<int> q;
int n,m,st;
int dis[MAXN];
signed main(){
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>st;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
	}
	q.push(st);dis[st]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].next,w=g[u][i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==INF) cout<<0x7fffffff<<" ";
		else cout<<dis[i]<<" ";
	}
	return 0;
}
2023/4/1 21:35
加载中...