三种最短路径算法(未完成)

Dijkstra算法（未完成）

用于计算一个原点到其他点的最短路径（不适用于有负数的权重）

初始化：

G[][2]二维数组存储邻接矩阵（如果权重没有0，那么没有边相连的存0可以，反之存无穷大）

dist[i]数组存储从原点到点i的最小距离，初始时 dist[原点] =0 ，dist[原点相连接的点]= 距离（权重），dist[其余的点]=无穷大

n=节点数,m=边数

p[i] = i这个点的前驱点

vis[i]= i这个点是否加入S集合 bool型

首先分为两个集合 S 和 V-S 其中每考虑完一个节点就把那个节点加入S集合。

1.找最小

2.更新

O(n^2)的时间复杂度用优先队列写可以优化到O(nlogn)

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
typedef pair<int ,int> pii; 
const int M=999999;

int p[10],G[10][10],dist[10];
int n=5 ,m=8 ; //节点数，边数 
bool vis[10];

void dijkstra(int u){
	for(int i=1;i<n;++i){
		int tmp=M,t=u;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&dist[j]<tmp){
				tmp=dist[j];
				t=j;
			}
		}
		if(t==u) return;
		vis[t]=1;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&dist[j]>dist[t]+G[t][j]&&G[t][j]!=0){
				dist[j]=dist[t]+G[t][j];
				p[j]=t;
			}
		}
	}
}
void pri(int u){
	G[1][2]=2;
	G[1][3]=5;
	G[2][4]=6;
	G[2][3]=2;	
	G[3][4]=7;	
	G[3][5]=1;	
	G[4][3]=2;	
	G[4][5]=4;
	for(int i=1;i<n;++i){
		dist[i]==G[u][i];
		if(dist[i]==0)
			p[i]=u;
	}	
	vis[1]=1;
	memset(dist,M,sizeof(dist));
	dist[2]=2;
	dist[1]=0;
	dist[3]=5;
	p[3]=1;
	p[2]=1; 
}
void findp(int u){
	if(u==-1)
		return ;
		findp(p[u]);
		cout<<u<<" ";
}
int main(){
	pri(1);
	dijkstra(0);
	cout<<dist[5];
	return 0;
}

Bellman-ford算法

Floyd算法

用于计算各个顶点之间的最短路径

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
typedef pair<int ,int> pii; 
const int M=38758200196842127;
int G[2050][2050],dis[2050],p[2050];
bool vis[2050];
int n=2021;

int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
void fun(){
	//memset(dis,M,sizeof(int)*2050);
	for(int i=1;i<=n;i++){
		dis[i]=M;
		for(int j=1;j<=n;j++){
			if(i-j>21||i-j<-21)
				continue;
			G[i][j]=i/gcd(i,j)*j;
			G[j][i]=i/gcd(i,j)*j;
		}
	}
	for(int i=1;i<=n;i++){
		if(G[1][i]!=0)
			dis[i]=G[1][i];
	}
	vis[0]=1;
	vis[1]=1;
	
}

void fun2(int u){
	for(int i=1;i<n;i++){
		int tep=M,t=u;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&dis[j]<tep){
				tep=dis[j];
				t=j;
			}
		}
		if(t==u) return;
		vis[t]=1;
		for(int j=1;j<=n;++j){
			if(!vis[j]&&dis[j]>dis[t]+G[t][j]&&G[t][j]!=0){
				dis[j]=dis[t]+G[t][j];
				p[j]=t;
			}
		}
	}
	
}
signed main(){
	fun();
	
	fun2(0);
	cout<<dis[2021]<<endl;	
	return 0;
}