一个自己捣鼓出来的最短路径算法，有若干问题，欢迎各路神仙来看看

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

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

下面是我的代码。

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

一个自己捣鼓出来的最短路径算法，有若干问题，欢迎各路神仙来看看

讨论操作

回复

相关推荐

一个自己捣鼓出来的最短路径算法，有若干问题，欢迎各路神仙来看看