SPFA、迪杰斯特拉、弗洛伊德算法C++实现

三者不同，就我个人理解而言，迪杰斯特拉是求单源点最短路径且权值为非负，算法效率为：；弗洛伊德算法是求任意两点间的最短路径，算法复杂度高，为；SPFA为单源点最短路径，权值可为负数，时间复杂度为；三者均可以处理有向和无向图。

且我觉得你只要会了SPFA，另外两种都可以解决，SPFA既可以求负值也可以求解正的权值，再多加一层for循环那么弗洛伊德求任意亮点最短路径也可以解决。

第一种写法：vector+结构体

#include 
using namespace std;
const int INF = 0x3f3f3f3f;

struct node{
	int v,weight;
};
vector V[MAX];  //二维动态数组
int vis[MAX],dis[MAX];  //dis[i]用以存储源点dao点i的最短路径 vis[i]为点i是否在队列中 
void SPFA(int src){
	queue q;
	q.push_back(src);
	vis[src]=1;
	dis[src]=0;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(int i=0;i>u>>v>>w;
		node t;
		t.v=v;
		t.weight=w;
		V[u].push_back(t);
		t.v=u;
		V[u].push_back(t);  //两个同时push表明为无向图 若有向图只push一个值即可 
	}
	SPFA(s);
	cout< 
第二种写法：vector+pair，基本差不多，看起来会简洁一些
 
#include
using namespace std;

const int MAX = 1e5+10;
const int INF=0x3f3f3f3f;
typedef pair PII;

vector V[MAX];
int d[MAX],vis[MAX];

void SPFA(int src)
{
	memset(d,INF,sizeof d);
	queue q;
	q.push(src);
	vis[src]=1;
	d[src]=0;
	
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(auto k:V[t])
		{
			if(d[t]+k.second>n>>m;
	for(int i=0;i 
2.Dijkstra 
vector+堆优化
 
#include
using namespace std;

const int MAX = 1e5+10;
const int INF=0x3f3f3f3f;
typedef pair PII;

vector V[MAX];
int d[MAX],vis[MAX];

void Dijkstra()
{
	memset(d,INF,sizeof d);
	priority_queue,greater> q;
	q.push({0,1});
	d[1]=0;
	
	while(!q.empty())
	{
		PII t=q.top();
		q.pop();
		int ver=t.second;
		for(auto k:V[ver])
		{
			int j=k.first,w=k.second;
			if(d[ver]+w>n>>m;
	for(int i=0;i 
3.弗洛伊德 
DP可以解决，复杂度较高
 
#include 
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int d[N][N];
int n, m, k;

int main() {
    
    scanf("%d%d%d", &n, &m, &k);
    
    memset(d, 0x3f, sizeof d);
    for(int i=1; i<=n; i++) d[i][i] = 0;
    
    for(int i=0; i= INF/2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }
    
    
    return 0; 
}