洛谷 P3371 单源最短路

dijkstra 算法

可以求出从指定出发点到其他所有点的最短路径，但不能包含负权的边。

设集合 s 为已经求出来的点的集合，集合 v 为剩余待求的结点。

要求从 a 点出发，求出到所有点的最小权值，为达到目标，要将 v 集合中的结点一个一个地添加到 s 结点，当所有结点都在 s 集合中时，就完成任务了。

初始化：s 集合中只有 a  结点，其他所有结点都在 v 集合中。

每一步：选出从 a 出发，经过 s 集合更新后（经过 s 集合中哪些结点后到达目的地的距离是最短的）且目标节点在 v 中的一条路，这条路就是到这个目标节点的最短路，因为如果再经过 v 中的某个子集更新后，这条路不可能会更短。

时间复杂度：O(n^2)   PS：在求到达 v 集合中路径最短的一个结点时，可以用堆优化。

代码#include <iostream>

#include <cstring>
#include <vector>
using namespace std;

const int MAX = 10005;
const int INF = 2147483647;

struct Node{
    int v, len;
    Node(){}
    Node(int nv, int nl) : v(nv), len(nl){}
};

int n, m, s;
int vis[MAX];
int dist[MAX];
vector<Node> G[MAX];

int main(){
//    freopen("input.txt", "r", stdin);
    
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<=m; i++){
        int u, v, len;
        scanf("%d%d%d", &u, &v, &len);
        G[u].push_back(Node(v, len));
    }
    
    //dijkstra算法
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        dist[i] = INF;
    }
    dist[s] = 0;            //初始化，添加第一个点 
    vis[s] = 1;
    for(int i=2; i<=n; i++){        //添加第 2 到第 n 个点 
        for(int j=0; j<G[s].size(); j++){
            int u = s, v = G[u][j].v, len = G[u][j].len;
            dist[v] = min(dist[v], len + dist[u]);        //更新路径长度 
        }
        int minV, minLen = INF;
        for(int j=1; j<=n; j++){                //选出最短的 
            if(vis[j] == 0 && dist[j] < minLen){
                minLen = dist[j];
                minV = j;
            }
        }
        vis[minV] = 1;                    //添加这个点 
        s = minV;
    } 
    
    for(int i=1; i<=n; i++){
        if(i != 1)  printf(" ");
        printf("%d", dist[i]);
    }
    
    return 0;

}

SPFA 算法

有点像 BFS。

可以处理带负权边的图，但是图中不能存在负权回路。

初始化：起始点 a 加入队列。

每一步：当有一条路更新（有更短的路径）时，将该路径对应的结点（如果该结点在队列中，就不用重新放到队列了）加入队列（因为这条路更新了，所以可能通过这条路到达其他结点的距离也会更短）。当队列为空时，算法就结束了。

代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

struct Edge{
    int v, len;
    Edge(){}
    Edge(int nv, int nl) : v(nv), len(nl){}
};

const int MAX = 10005;
const int INF = 2147483647;

int n, m, s;
vector<Edge> G[MAX];
int vis[MAX];
int dist[MAX];


int main(){
//    freopen("input.txt", "r", stdin);
    
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<=m; i++){
        int u, v, len;
        scanf("%d%d%d", &u, &v, &len);
        G[u].push_back(Edge(v, len));
    }
    
    //SPFA 算法
    queue<int> que;            //存放结点的队列 
    memset(vis, 0, sizeof(vis));     //初始化 
    for(int i=1; i<=n; i++){
        dist[i] = INF;
    }
    vis[s] = 1;
    dist[s] = 0;
    que.push(s);
    while(!que.empty()){
        //进行松弛操作
        int u = que.front();  que.pop(); 
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].v;
            int len = G[u][i].len;
            if(dist[v] > dist[u] + len){    //如果到 v 有更短的路径 
                dist[v] = dist[u] + len;
                if(vis[v] == 0){            //将 v 结点放入队列，有可能从 v 出发会有到达其他结点更短的路 
                    que.push(v);
                    vis[v] = 1;
                }
            }
        }
        vis[u] = 0;
    }
    
    for(int i=1; i<=n; i++){
        if(i != 1)  printf(" ");
        printf("%d", dist[i]);
    }
    
    return 0;
}