朴素版本Dijkstra

适合于稠密图

不存在负权边

稠密图用邻接矩阵来存

初始化距离memset(dist,0x3f,sizeof dist);
初始化出发点距离为0

int g[N][N];
int dist[N];

int dijkstra(){
    
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    for(int i = 1;i <= n;i ++){
        int  t = -1;
        for(int j = 1;j <= n;j ++){
            if(!visit[j]&&(t==-1||dist[j]<dist[t])){
                t = j;
            }
        }
        visit[t] = true;
        
        for(int j = 1;j <=n;j++){
            dist[j] = min(dist[j],g[t][j]+dist[t]);
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f)return -1;
    
    return  dist[n];
    
}

堆优化版Dijkstra

适合稀疏图

约等于

稀疏图用邻接表来存

最短的点使用小根堆来优化
1号点距离为0，其他点初始化为正无穷，放入1号点

#include <priority_queue>

const int N = 1e5+10;


typedef pair<int,int> PII;


int h[N],e[N],ne[N],idx = 0;
int w[N];//用来存权重
int dist[N];
bool st[N];

int n,m;




void add(int a,int b,int c){
    w[idx] = c;
    e[idx] = b;
    ne[a] = h[a];
    h[a] = idx; 
}

int dijkstra(){
    memset(dist,ox3f,sizeof dist);
    
    priority_queue<PII,vector<PII>,greater<PII>> heap; // 定义小根堆  
    
    heap.push({0,1}); // 根据距离来排序 ({距离，点位})
    
    dist[1] = 0;
    
    while(heap.size()){
        
        auto k = heap.top();
        
        heap.pop();

        int pot = k.second;
        
        int distance = k.first;
        
        if(st[k])continue;
        
        st[k] = true; // 标记
        
        for(int i = h[pot];~i;i = ne[i]){
            int j = e[i] ; // e中存的是下标[i]对应的点  头
            if(dist[j] > distance+w[i]){
                dist[j] = distance + w[i]; // 更新j点点位
                heap.push({dist[j],j});
            }
            
            
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f)return -1;
    
    return  dist[N];  
}


int main(){
    
    
    memset(h,-1,sizeof h); // 所有头为0
    
    int n,m;
    cin >> n>>m;
    
    while(m --){
        int a,b,c;
        cin >> a>>b>>c;
        add(a,b,c);
    }
    
    
    return 0;//
}

bellman_ford

存在负权边

有边数限制的最短路问题

走过k条边后任意点到1的距离
走过k条边后判断n点又没有走过

时间复杂度

AcWing 853. 有边数限制的最短路（Bellman-Ford） - AcWin


const int N = 510,M=1e5+10,INF = 0x3f3f3f3f;

typedef struct {
    int a,b,c;
}Edge;

Edge edge[M];
int dist[N],last[N]; //路径长度，上次迭代的值


void Bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]  = 0;
    
//    k次迭代  表示从不超过k开始的最短路的距离
    for(int i=0;i < k;i++){
        memcopy(last,dist,sizeof dist);
        for(int j=0;j<n;j++){  //枚举每个边
            Edge e = edge[j];
            dist[e.b] = min(dist[e.b],last[e.a]+e.c);
        }
    }
    
}

spfa

堆优化版的bellman_ford

可以存在负权边 不可以存在负权回路
求负环可以使用spfa算法 cnt 计入每个点到原点的边数某个点被更新就+1,边数达到了n就说明有负环
n和原点不连通不更新

#include <queue>
typedef pair<int,int> PII;


const int N = 1e5+10;

int h[N],e[N],ne[N],w[N],idx = 0;


int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}


int spfa(){

    queue<PII> q;
    
    q.push({0,1}); // distance , pot;
    dist[1] = 0;
    st[1] = true;
    
    memset(dist,0x3f,sizeof dist);
    
    while(q.size()){
        PII p = q.front();
        q.pop();
        int pot = p.second;
        st[t] = false;
        
        for(int i=h[t];~i;i = ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+w[i]){
                
               // cnt[j] = cnt[t]+1; //从1 到n的边数
               // if(cnt[j]>=n)return true;//判断出有负权回路
                
                dist[j] = dist[t] + w[i];       
                if(!st[j]){
                    st[j] = 1;
                    q.push({dist[j],j});                
                }
            }
        }
        
    }
    
    if(dist[n] == 0x3f3f3f3f)return -1;
    return dist[n];
    //return false;//没有负权回路
}


int main(){
    memset(h,-1,sizeof h);
    
    
    return 0;
}

floyd

时间复杂度（）

n代表点数

用于求多源最短路问题

int d[N][N];
void floyd(){
    for(int k = 0;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                d[i][j]  = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }  
}