2020.02.11

I learned it today djs Algorithm , Let's summarize .

This algorithm is to find the shortest path of a single source . Now I'll give you the template and ideas , Be clear at a glance .

#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;
}