Floyd Dijkstra

//dp 
//O(n^3)  边权可为负  所有点队之间 
//使用场景：边权有负，图规模小，需要判断负环 ,稠密图 
//n<=300
//思路：与完全背包相同 
#include<bits/stdc++.h>
using namespace std;
//基础
const int MAXN=305; 
int n,m,b,dp[MAXN][MAXN][MAXN];
int main(){
	memset(dp,0x3f,sizeof(dp)); //初始化 0x3f表示无穷大 
	for(int i=1;i<=n;i++) dp[0][i][i]=0; //走到自己的最小值为0 
	scanf("%d%d%d",&n,&m,&b); //n:点数 m:边数 b:起点 
	for(int i=1;i<=m;i++){
		int from,to,w;
		scanf("%d%d%d",&from,&to,&w);
		dp[0][from][to]=w;
	}
	for(int k=1;k<=n;k++) //遍历"中转站" 
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);
    //dp[k-1][i][j]：不走"中转站"  dp[k-1][i][k]+dp[k-1][k][j]:走"中转站"([i][k]:i->k [k][j]:k->j); 
    for(int e=1;e<=n;e++)
    	if(e!=b) printf("%d ",dp[n][b][e]);
    return 0;
}
//动态优化 
const int MAXN=305; 
int n,m,b,dp[MAXN][MAXN]; //同DP背包，该代码只调用k-1的值故可以由三维降为二维 
int main(){
	memset(dp,0x3f,sizeof(dp)); 
	scanf("%d%d%d",&n,&m,&b);
	for(int i=1;i<=n;i++) dp[i][i]=0; 
	for(int i=1;i<=m;i++){
		int from,to,w;
		scanf("%d%d%d",&from,&to,&w);
		dp[from][to]=w;
	}
	for(int k=1;k<=n;k++)//不用考虑无后效性 
		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]);
    for(int e=1;e<=n;e++)
    	printf("%d ",dp[b][e]);
    return 0;
}

//BFS+贪心 
//O(n^2) 边权不可为负  所有点对之间 
//使用场景： 最常用最高效的算法，一个起点到其他所有的点的最短路 
//n<=5000
//思路：BFS遍历，删去每次出现的最小边 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+2,INF=0x3f3f3f3f;
int n,m,be,ans[MAXN];
bool flag[MAXN]={false};
struct edge{
	int to,w;
};
vector<edge>e[MAXN];
struct s{
	int num,poi;
}min1,min2;
/*定义最小值和次小值是因为
根据定义，每次的始点是还未得出最小值的点中的的最小值所对应的点
如果只设置最小值，将只会表示now所可以到达的点中的最小值，比定义的区间小存在错误
故而设置两个点*/ 
void dfs(int now,int step){
	/*根据定义，每次求出一个点的答案，则只需n-1步就可以求出使用的点
	用于判断是否全部求出以免死循环*/ 
	if(step>=n) return ;
	for(edge i:e[now]){
		if(flag[i.to]==true) continue; //如果已经得出最小值的点跳过 
		ans[i.to]=min(ans[i.to],ans[now]+i.w); //对于第i个点的最小值更新
		if(min1.num>ans[i.to]){ //如果比当前存储的最小值小 
			if(i.to!=min1.poi){ 
			/*如果第i个点已经是还未更新的最小值的点，只对最小值进行修改不用存储原本为更新的最小值 
			如果第i个点不是还未更新的最小值的点，则需要对原本最小值进行继承，即将次小值修改为原本的最小值*/
			    //继承 
				min2.num=min1.num;
	    		min2.poi=min1.poi;
			}
			//更新 
			min1.num=ans[i.to]; 
			min1.poi=i.to;
		}else if(min2.num>ans[i.to]&&i.to!=min1.poi){
			min2.num=ans[i.to];
			min2.poi=i.to;
		}
	}
	/*根据定义，每次dfs的起始点是还未得出最小值的点中的的最小值所对应的点*/ 
	int next=min1.poi;
	/*最小值的点的答案已经得出，将最小值更新为次小值*/ 
	min1.poi=min2.poi;
	min1.num=min2.num;
	min2.num=INF;
	/*标记原最小值的点，表示已被求出*/ 
	flag[next]=true;
	dfs(next,step+1);
}
int main(){
	scanf("%d%d%d",&n,&m,&be);
	memset(ans,0x3f,sizeof(ans));
	ans[be]=0,flag[be]=true;
	min1.num=INF,min2.num=INF;//存储最小值初始化正无穷。 
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		e[a].push_back({b,c});
	} 
	dfs(be,1);
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
}