Some things can not be relieved for a long time, so recently learned the next shortest path algorithm, I hope I can become more relaxed.

dijkstra is a single source shortest path algorithm. In the graph without negative weight, vi..vj..vk is the shortest path from vi to vk, so we must take the shortest path from vi to vj. So each time the minimum distance from the starting point is taken out, the distance between adjacent points is updated from that point, and if the update is successful, the new point is added to priority_queue. Storage graphs use adjacency tables. The code is as follows:

#include <bits/stdc++.h>//Directed graph
using namespace std;
//dijkstra Not applicable to graphs with negative weights
const int maxn = 1007, maxm = 20007, INF = 2147483467;// maxn It is slightly larger than the number of vertices. maxm Slightly larger than edges
int head[maxn], vis[maxn], dis[maxn], fa[maxn];
int next[maxm], u[maxm], v[maxm], w[maxm];
typedef pair<int, int> pi;// pair The ranking strategy is to rank first. pair Put the distance ahead and the point behind.
int n, m;
void ini()
{
    memset(vis, 0, sizeof(vis));//At first all points were left untreated.
    memset(head, -1, sizeof(head));//All points have no boundaries.
    for(int i = 0; i <= n; i++)
        dis[i] = INF;//The distance from the starting point to all points is infinite.
}

void dij(int s, int e)
{
    priority_queue<pi> Q;//Priority queue
    dis[s] = 0;
    Q.push(make_pair(dis[s], s));
    while(!Q.empty())
    {
        pi u = Q.top();
        Q.pop();//take out d The smallest point
        int x = u.second;
        if(x == e)
            break;
        if(vis[x])//Handled, skipped
            continue;
        vis[x] = 1;
        for(int i = head[x]; ~i; i = next[i])//Update from the current d The minimum distance between adjacent points
        {
            if(dis[v[i]] > dis[x] + w[i])
            {
                dis[v[i]] = dis[x] + w[i];//Relaxation Success
                fa[v[i]] = x;
                Q.push(make_pair(dis[v[i]], v[i]));//Join the queue with successful update points
            }
        }
    }
    if(dis[e] == INF)
        return;//s reach e no path
    vector<int> ans;//use vector Finding a path from the end to the beginning can also be done by recursion.
    int temp = e;
    while(temp!=s)
    {
        ans.push_back(temp);
        temp = fa[temp];
    }
    ans.push_back(s);
    for(int i = ans.size()-1; i >= 0; i--)
        printf("%d ", ans[i]);
    printf("\n%d\n", dis[e]);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        ini();
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", u+i, v+i, w+i);
            next[i] = head[u[i]];
            head[u[i]] = i;//Establishing Adjacency List
        }
        int S, E;//Starting point end point
        scanf("%d%d", &S, &E);
        dij(S, E);
    }
    return 0;
}

The classical comparison of dijkstra requires that negative weights should not be included, so we learned how to deal with spfa with negative weights.

spfa feels a bit like bfs, but BFS only processes one node once, and if spfa relaxes the nodes passing through the path, it will update all the points after the path. If there is a negative ring, the distance decreases every time the negative ring is traveled, and there is no shortest path, so it is assumed that there is no negative ring (or whether there is a negative ring). The code is as follows:

#include <bits/stdc++.h>//Directed graph
using namespace std;
const int maxn = 1007, maxm = 10007, INF = 2147483467;
int head[maxn], in[maxn], dis[maxn], fa[maxn];//in Marked at queue Midpoint
int u[maxm], v[maxm], w[maxm], next[maxm];
int n, m;

void ini()
{
    memset(in, 0, sizeof(in));
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= n; i++)
        dis[i] = INF;
}

void print(int s, int e)//Recursive Printing Path
{
    if(e!=s)
        print(s, fa[e]);
    printf("%d ", e);
}

void spfa(int s, int e)//something like bfs，However bfs Does not handle previously processed points
{
    queue<int> Q;
    dis[s] = 0;
    in[s] = 1;
    Q.push(s);
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        in[x] = 0;
        for(int i = head[x]; ~i; i = next[i])
        {
            if(dis[v[i]] > dis[x] + w[i])
            {
                dis[v[i]] = dis[x] + w[i];
                fa[v[i]] = x;
                if(!in[v[i]])
                   {
                       Q.push(v[i]);
                       in[v[i]] = 1;
                   }
            }
        }
    }
    print(s, e);
    printf("\n%d\n", dis[e]);
}
int main()
{
    freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        ini();
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", u+i, v+i, w+i);
            next[i] = head[u[i]];
            head[u[i]] = i;
        }
        int s, e;
        scanf("%d%d", &s, &e);
        spfa(s, e);
    }
    return 0;
}

There is a floyd algorithm for multi-source shortest path, which is actually discrete warshall closure: (but because time complexity O (n^3) is a bit disgusting 2333), it has not been implemented by itself, the core code is as follows:

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(g[i][j] > g[i][k] + g[k][j])
                    g[i][j] = g[i][k] + g[k][j];

The idea is to start using adjacency matrix to store graphs. Updating the distance between two points can only depend on transiting through other points, so one point (i.e. the first cycle) is allowed at a time, and the shortest path (the second triple cycle) is considered.

The advantage of floyd is that the code is short and the shortest path between all nodes can be found at one time.

Today's harvest is quite great. To sum up, we use dijkstra for dense/negative weight maps, spfa for sparse/negative weight maps and floyd for time requirements.

(Still in a bad mood)