The third chapter of the basic algorithm series -- the shortest path problem in graph theory

There are five commonly used shortest path algorithms in graph theory. They are coming. All the villains are coming 💣 The enemy has five seconds to reach the battlefield~

💓 On graph theory

Graph theory has a long history, but graph theory is an important concern in both company interview and programming competition. Now there may be many partners preparing for the Blue Bridge Cup. Here is the test point on graph theory pasted by the author from the official website of the Blue Bridge Cup.

Graph theory is also a regular guest in the interview

For this article, the author summarizes and shares the shortest path problem in the test site, and other graph theory problems continue to emerge in the follow-up~

🌟 Knowledge foreshadowing

🌻 Definition of graph

A graph is generally defined and described by a binary g = (V, e) or g = < V, E >. Where V is the set of vertices of graph G and E is the set of edges in graph G.
Parentheses "()" are used to indicate an undirected graph
Sharp angle brackets "< >" are used to represent a directed graph
	For a directed graph, we generally use two storage methods: adjacency matrix and adjacency table. For an undirected graph, we can regard an undirected graph as two directed edges with opposite directions, so an undirected graph can be regarded as a special directed graph, so we will only discuss the directed graph in the following examples

🌻 adjacency matrix

To put it more simply, it is to map the information given in the title to a two-dimensional matrix.

In combination with the above figure, point 0 can go to point 1. In the two-dimensional matrix on the right, point 1 and point 0 on the position mark corresponding to (0,1) cannot go to point 2. Let (0,2) still be point 0, point 0 can go to point 3, let (0,3) mark 1, and so on

🌻 Adjacency table

To be simple and rough is to string some connected points into a linked list according to the information given by the topic

Still use the village example just now. Point 4 can go to points 2, 5 and 9, and then string them on a linked list. Write the whole 0 ~ 9 points side by side

💓 General outline of shortest path algorithm

Friends, in this picture, you should keep in mind how to use the corresponding types of shortest path algorithms under different backgrounds and the time complexity of each shortest path algorithm 😉

💓 dijkstra algorithm

🌟 Naive dijsktra algorithm (applicable to dense graphs)

🌻 Example description


Portal

It is stated in the title that there is no negative weight edge. According to the data range given in the title, there are few points and many edges. Therefore, it can be found that it is a dense graph, so it can be solved directly with the simple version of dijkstra.

🌻 Reference code (C + + version)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N  = 510;

int n,m;					//Points and edges in a graph
int g[N][N];				//adjacency matrix 
int dist[N];				//Represents the distance from point 1 to each point in the figure
bool st[N];					//Store the identified shortest point

//Complete the function called
void dijkstra()
{
    
    memset(dist,0x3f,sizeof dist); //To process the distance array dist, first set all points to positive infinity
    dist[1] = 0;                  //Handle point 1, indicating that the distance from point 1 to point 1 is 0

    //n-1 cycles
    for(int i = 0; i < n-1;i++)
    {
        int t = -1;
        //Process each point
        for(int j = 1; j <= n;j++)
        //If the current j is not in the st record status array
        //T = = - 1 | dist [t] > dist [j] means that this t was previously assigned by other j, and now a better one appears, or the value of this t has not been modified directly
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;

        st[t] = true;			//Put this point into the set

        //Use t to update the distance from other points to point 1
        for(int j = 1; j <= n;j++)
            dist[j] = min(dist[j],dist[t]+g[t][j]);
    }
}

int main()
{
    //Enter points and edges
    scanf("%d%d",&n,&m);

    //Initialize adjacency matrix
    memset(g,0x3f,sizeof g);

    //m times of inquiry and the process of drawing construction
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //Save to the drawing, just deal with the heavy edges
        g[a][b] = min(g[a][b],c);
    }

    //Call dijkstra
    dijkstra();

    //Output results
    if(dist[n] == 0x3f3f3f3f) printf("%d",-1);
    else  printf("%d\n",dist[n]);

    return 0;
}

🌻 Algorithm template

The specific operation flow of the simple dijkstra algorithm can be described in the following figure:

The specific code template of the simple dijkstra algorithm is as follows:

	int g[N][N];  // Store each edge
	int dist[N];  // Store the shortest distance from point 1 to each point
	bool st[N];   // Store whether the shortest circuit of each point has been determined

	void dijkstra()
	{
		//Initialization link
		memset(dist, 0x3f, sizeof dist);
		dist[1] = 0;

		for (int i = 0; i < n - 1; i ++ )
		{
			int t = -1;		// Find the point with the smallest distance among the points where the shortest path has not been determined
			for (int j = 1; j <= n; j ++ )
				if (!st[j] && (t == -1 || dist[t] > dist[j]))
					t = j;
					
			st[t] = true;

			// Update the distance of other points with the global minimum variable t
			for (int j = 1; j <= n; j ++ )
				dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}

🌻 Detail implementation

1, Heavy edge

When building a graph, we need to focus on dealing with multiple edges, and finally only leave the shortest edge to build the graph
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        /use min The function filters out the shortest edge to build the graph
        g[a][b] = min(g[a][b],c);
    }

2, The idea of initialization

Use the memset function to initialize the given address in bytes. Because it is to find the minimum path, initialize the distance from point 1 to each point as a large data, and finalize the distance from point 1 to point 1 as 0
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

3, Find the point with the smallest distance among the points where the shortest path has not been determined

The core of the whole code is "! st[j]", and all operations are carried out at the point j currently ready to explore without being determined.
For: int t = -1; It means that a variable t is declared to record the minimum value for the whole world. At the beginning, it is assigned a non-existent - 1. Using this minimum value to update all its outgoing edges is also carried out according to the idea of finding the global minimum value, so the shortest path can be obtained at last

Finally, after all n points have been tried, put the global minimum variable t into the array st in which the shortest path state has been determined, "st[t] = true"

		for (int i = 0; i < n - 1; i ++ )
		{
			int t = -1;		
			for (int j = 1; j <= n; j ++ )
				if (!st[j] && (t == -1 || dist[t] > dist[j]))
					t = j;
					
			st[t] = true;

😉 Happy Ac

🌟 Heap optimized dijkstra algorithm (applicable to sparse graph)

It can be seen from the above program code that its time complexity is O(n2). The main bottleneck affecting efficiency is to find the global minimum variable. Here, it enumerates next to next, and the efficiency will be relatively poor

Therefore, a heap can be used to maintain the dist array. The minimum value can be obtained in O(logn) time and deleted from the heap. Then an edge can be expanded and updated in O(logn) time. Finally, O(mlogn) can be used to realize the heap optimized version of dijkstra algorithm.

🌻 Example description


Portal

🌻 Reference implementation code (C + + version)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int,int> PII;     //Use a pair number to maintain the distance and node number
int n,m;
const int N = 1e6+10; 
int h[N],e[N],ne[N],w[N],idx;   //Sparse graph, saved with adjacency table
int dist[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++;
}

void dijkstra()
{
    //Initialization link
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    //Create a small root heap using the STL container
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1}); //The first attribute of the number pair is the distance, and the second attribute is the node
    
    //Operate when the heap is not empty
    while(heap.size())
    {
        //Take out the point with the smallest current distance each time. For the small root heap, that is, the top of the heap
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if(st[ver]) continue; //If this node is already in st, it means that redundant backup is being explored. Just skip it
        
        st[ver]  =true;     //Mark this node to determine the shortest path
        
        //Update other points with the current point
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            //Get the node stored in the adjacency table and store the node data in j
            int j = e[i];
            //Start update
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});  //Insert the updated data into the heap
            }
        }
    }

}


int main()
{
    //input
    scanf("%d%d",&n,&m);
    //Initialize adjacency table
    memset(h,-1,sizeof h);
    //Construction drawing according to m edges
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    
    //Call dijkstra function
    dijkstra();
    //output
    if(dist[n] == 0x3f3f3f3f) puts("-1");
    else printf("%d",dist[n]);
    
    return 0;
}

🌻 Algorithm template

The operation flow of dijkstra algorithm of heap optimization version can be shown in the following figure:

The code of heap optimized dijkstra algorithm is described as follows:

typedef pair<int, int> PII;

	int n,m;							// Number of points
	int h[N], w[N], e[N], ne[N], idx;	// The adjacency table stores all edges
	int dist[N];						// Store the distance from all points to point 1
	bool st[N];							// Is the shortest distance to store each point determined

	void dijkstra()
	{
		memset(dist, 0x3f, sizeof dist);
		dist[1] = 0;
		priority_queue<PII, vector<PII>, greater<PII>> heap;
		heap.push({0, 1});		// first storage distance, second storage node number

		while (heap.size())
		{
			auto t = heap.top();
			heap.pop();

			int ver = t.second, distance = t.first;

			if (st[ver]) continue;
			st[ver] = true;

			for (int i = h[ver]; i != -1; i = ne[i])
			{
				int j = e[i];
				if (dist[j] > distance + w[i])
				{
					dist[j] = distance + w[i];
					heap.push({dist[j], j});
				}
			}
		}
	}

🌻 Detail implementation

1, Establishment of adjacency table

The idea is as like as two peas, but only one weight should be recorded. If you are not familiar with the static list, you can look at this buddy.

Data structure - good helper for competition, static linked list

2, It is recommended to memorize the line of code for creating a small root heap

3, Data acquisition

After obtaining the heap top, continue to obtain the corresponding distance, node number and other data through the first and second attributes

Chic Ac

💓 Bellman Ford algorithm

Look back at the algorithm outline 😉

Bellman Ford algorithm and SPFA algorithm are used in the context of single source and negative weight edge. On the whole, SPFA is better than Bellman Ford algorithm, but for the shortest path problem with limited number of edges, Bellman Ford algorithm can only be used

🌻 Example description - shortest path with edge number limit


Portal

🌻 Reference code (C + + version)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510 , M = 10010;
int n,m,k;
int dist[N];
int backup[N];
//Structure of storage point and weight
struct Edge{
    int a,b,w;
}edges[M];

void bellman_ford()
{
    //Initialization link
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    //Iterative k-edges
    for(int i = 0 ; i < k ; i++)
    {
        //backups
        memcpy(backup,dist,sizeof dist);
        //Deal with the shortest circuit on each side
        for(int j = 0; j < m;j++)
        {
            //Get information for each point
            int a = edges[j].a,b = edges[j].b,w = edges[j].w;
            //Find shortest path
            dist[b] = min(dist[b],backup[a]+w);
        }
    }
}
int main()
{
    //input
    scanf("%d%d%d",&n,&m,&k);
    //Mapping
    for(int i = 0; i < m ;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i] = {a,b,w};
    }
    //Call function
    bellman_ford();
    //Output results
    if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n",dist[n]);
    
    return 0;
}

🌻 Algorithm template

The flow chart of Bellman Ford algorithm implementation is as follows:

The bellman Ford algorithm code is described as follows:

	int n, m;		// n represents the number of points and m represents the number of sides
	int dist[N];		// dist[x] stores the shortest distance from 1 to X

	struct Edge		// Edge, a represents the point, b represents the entry point, and w represents the weight of the edge
	{
		int a, b, w;
	}edges[M];

	void bellman_ford()
	{
		memset(dist, 0x3f, sizeof dist);
		dist[1] = 0;

		// If the n-th iteration still relaxes the trigonometric inequality, it indicates that there is a shortest path with a length of n+1. According to the drawer principle, there are at least two identical points in the path, indicating that there is a negative weight loop in the graph.
		for (int i = 0; i < n; i ++ )
		{
			for (int j = 0; j < m; j ++ )
			{
				int a = edges[j].a, b = edges[j].b, w = edges[j].w;
				if (dist[b] > dist[a] + w)
					dist[b] = dist[a] + w;
			}
		}
	}


🌻 Detail implementation

1, Backup - in order to ensure that the condition of edge number limit can not be broken

        memcpy(backup,dist,sizeof dist);

In order to avoid this, although the operation is indeed carried out under the number of sides k of the outer loop, a similar situation occurs when the inner loop goes to explore the point, so a backup operation is taken to curb this situation


2, Happy Ac

💓 SPFA algorithm

spfa is usually called "Bellman Ford algorithm for queue optimization" internationally

🌻 Example description

🌻 Reference code (C + + version)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[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 ++ ;
}

void spfa()
{
    //Initialization link
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    //Create a queue and queue point 1 that has confirmed the shortest path
    queue<int> q;
    q.push(1);
    //Mark points that have been queued
    st[1] = true;

    //Perform a series of operations when the queue is not empty
    while (q.size())
    {
        //Get the team leader and get the team leader out of the team
        int t = q.front();
        q.pop();
        //Mark points that are not in the queue
        st[t] = false;
        //Use the team head to explore its exit
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                //If the conditions are met, update the distance from point 1 to j
                dist[j] = dist[t] + w[i];
                //If this point is not in the queue
                if (!st[j])
                {
                    //Join the team, mark
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    //input
    scanf("%d%d", &n, &m);
    //Initialize adjacency table
    memset(h, -1, sizeof h);
    //Mapping
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    //Call function
    spfa();
    //output
    if (dist[n] == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}

🌻 Algorithm template

The flow chart of SPFA algorithm implementation is as follows:

The code of SPFA algorithm is described as follows:

	int n;									// Total points
	int h[N], w[N], e[N], ne[N], idx;		// The adjacency table stores all edges
	int dist[N];							// Store the shortest distance from each point to point 1
	bool st[N];								// Stores whether each point is in the queue

	void spfa()
	{
		memset(dist, 0x3f, sizeof dist);
		dist[1] = 0;

		queue<int> q;
		q.push(1);
		st[1] = true;

		while (q.size())
		{
			auto t = q.front();
			q.pop();

			st[t] = false;

			for (int i = h[t]; i != -1; i = ne[i])
			{
				int j = e[i];
				if (dist[j] > dist[t] + w[i])
				{
					dist[j] = dist[t] + w[i];
					if (!st[j])		// If j already exists in the queue, there is no need to insert j repeatedly
					{
						q.push(j);
						st[j] = true;
					}
				}
			}
		}
	}

🌻 Detail implementation

1, Team entry and marking

After updating the new point j with t, remember to judge whether this point has been marked. If not, add it to the queue and put it into the st array for marking

2, Associative memory

The essence of SPFA is to optimize the bellman Ford algorithm with queues, but the implementation is very similar to the heap optimized version of dijkstra algorithm, the queue for SPFA and the priority queue for dijkstra

Happy Ac

💓 Floyd algorithm

In order to find the shortest path between any two points in the graph, that is Shortest path outline The shortest path problem of multiple sources and sinks in. For the shortest path problem between any two points, the graph is generally dense and the implementation is very simple.

The idea of Floyd algorithm:
Split the multi-source shortest path into N times of single source shortest path.
In Dijkstra algorithm, the single source shortest path uses two cycles. The time complexity is O (N2). Floyd sets a layer of cycle n in the outermost layer, so the time complexity is O(n3)

🌻 Example description

🌻 Reference code (C + + version)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 210,INF = 1e9;
int n,m, Q;
int d[N][N];

void floyd()
{
    for(int k = 1; 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]);
}


int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    
    //Initialize adjacency matrix
    for(int i = 1;i <= n;i++)
        for(int j = 1; j <= n;j++)
        if(i == j) d[i][j] = 0;
        else d[i][j] = INF;
    
    //Create diagram
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        
        d[a][b] = min(d[a][b],c);
    }
    
    //Call function
    floyd();
    
    //Handle Q queries
    while(Q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        
        if(d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n",d[a][b]);
    }
    return 0;
}

🌻 Algorithm template

Flow chart of Floyd algorithm implementation:

Floyd algorithm code Description:

initialization:
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= n; j ++ )
				if (i == j) d[i][j] = 0;
				else d[i][j] = INF;

	// After the algorithm, d[a][b] represents the shortest distance from a to B
	void floyd()
	{
		for (int k = 1; 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]);
	}

🌻 Detail implementation

1, Initialization

				if (i == j) d[i][j] = 0;
				else d[i][j] = INF;
d array represents the distance from i to j, so during initialization, i == j should be initialized to 0, and other positions should be initialized to an infinite number

2, Output

Because the edge weight can be negative, d[a][b] is not necessarily INF, so the judgment condition is changed to d[a][b] is still a relatively large number
        if(d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n",d[a][b]);

Thank you for your patience ~, if you are biased, please point it out in a private letter in time 💖💖💖

Continuous updat ing of basic algorithm~

Keywords: Algorithm Graph Theory dijkstra

Added by andrewcy on Thu, 13 Jan 2022 02:03:06 +0200