2022.02.14

I didn't learn anything new today , I finished the problem set . I will summarize the single source shortest path algorithm and optimization .

First we have to understand its idea , It must be single source , The second is to find the shortest distance from a fixed point to another point .

And there can be no negative weight edge .

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f; // infinity , Not adjacent is infinite 
int G[N][N], dis[N];        // G Is the adjacency matrix ,dis Single source to i A weight 
int p[N];                   // Record the precursor 
bool book[N];               // Determine whether it has been added to the set , The set represents the updated nodes 
int n;
void dijkstra(int u, int n) // u It's the source , The shortest path from the source point to each vertex ,n It's a fixed number 
{
    for (int i = 1; i <= N; i++) // initialization 
    {
        dis[i] = G[u][i];
        book[i] = 0;
        /*
        if (dis[i] == INF) // If it is equal to INF, Express u Can't reach this vertex , The precursor is -1
            p[i] = -1;
        else
            p[i] = u;
            */
    }
    dis[u] = 0;                 // u To u A weight of 0
    book[u] = 1;                // Express u Updated 
    for (int i = 1; i < n; i++) // Find the smallest and update dis
    {
        // printf("=============\n");
        int min = INF, t = u;
        for (int j = 1; j <= n; j++)
            if (!book[j] && dis[j] < min) // If j Not updated and adjacent 
            {
                min = dis[j];
                t = j;
            }
        if (t == u) // Optimize 
            return;
        book[t] = 1;
        // printf("t:%d\n", t);
        for (int j = 1; j <= n; j++)
        {
            if (!book[j] && dis[j] > dis[t] + G[t][j]) // If a vertex is at the same time and u and t Adjacency , Update dis[j] Value 
            {
                // printf("dis[j]:%d\n", dis[j]);
                dis[j] = dis[t] + G[t][j];
                // p[j] = t; // change j The precursor of t
                //  printf("dis[j]:%d\n", dis[j]);
            }
        }
    }
}
int main()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            G[i][j] = INF;
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++)
            cin >> G[i][j];
    dijkstra(1, n);
    cout << dis[3] << endl;
}

This is dijkstra The template of , While seeking the shortest path, it also saves its precursor , It is convenient to change the output path .

It's not hard to understand , Mainly for dijkstra The optimization of the , There are two ways to optimize , One is heap optimization , The other is chain forward star optimization , These two optimizations optimize the simple from different angles dijkstra Algorithm , So as to reduce the time complexity . Add here dijkstra The time complexity of the naive algorithm is O（n^2）, If we use the optimized algorithm , It can make the time complexity reach nlogn The level of . Let me explain the principle and process of optimization .

The first is heap optimization .

Heap optimization refers to the operation of using the priority queue to stack our edges and weights . Priority queues are different from the queues we normally use , Priority queue at C++ in STL Overloads are defined in the container , When we use it, we sort by default , It consists of a large top pile and a small top pile . The two sorts mean that the top elements of the stack are different . The top layer of the big top stack must be the largest , On the contrary, the small top pile is the smallest . The sorting method is the construction of balanced binary tree through array . This means that no matter how many layers we construct , You only need to traverse each time you sort logn The corresponding position can be found and exchanged , Ensure the nature of our priority queue . So if we use priority queues , You can optimize in the search section , Reduce time complexity .

The second is the chain forward star .

This chained forward star is a chained structure simulated by an array

void add(int u, int v, int w)
{
    to[++cnt] = v;
    val[cnt] = w;
    next1[cnt] = head[u]; // Reverse storage , It doesn't affect the result 
    head[u] = cnt;
}

Using arrays next To store the edges that share the starting vertex with it , for instance 1->2,1->5 So when storing ,2 and 5 Will be linked , The advantage of this is to reduce the use of adjacency matrix .