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]);
    }
}