Search and Graph Theory (II)

This is the shortest.

The most common short-circuit problems are generally divided into two categories:

  • Single source shortest circuit
  • Multi-source sink has the shortest circuit

In the shortest path problem, the source is the starting point and the sink is the end point.

Single source shortest circuit

The shortest path in a single source is the shortest distance from one point to all the other points. (The starting point is fixed and single)

Depending on whether there is an edge with negative weight, there are two cases

  • All the edges have a positive weight

    There are usually two algorithms

    • Simple Dijkstra

      Time complexity O(n^2^), where n is the number of points in the graph and m is the number of edges

    • Heap optimized version of Dijkstra

      Time complexity O(Mlogn)

    Which one is better or worse depends on the density of the graph (depends on the number of points n in relation to the number of edges M). When the graph is sparse (n and M are at the same level), maybe heap-optimized version of Dijkstra is better. When it is dense (m and n^2^ are of the same order), it is better to use naive Dijkstra.

  • There are edges with negative weights

    There are usually two algorithms

    • Bellman-Ford

      Time complexity O(nm)

    • SPFA

      The time complexity is generally O(m) and the worst O(nm), which is the optimized version of the former. However, in some cases, SPFA cannot be used and only the former can be used. For example, bellman-Ford can only be used when the shortest circuit is required to be less than K edges

Multi-source sink has the shortest circuit

Find the shortest path from multiple starting points to other points. (Starting points are not fixed, but multiple)

Floyd algorithm (time complexity O(n^3^))

The core of the shortest circuit problem lies in abstracting the problem into a shortest circuit problem and drawing it. Graph theory-related problems do not focus on algorithm principles, but on the abstraction of the problem.

Dijkstra is based on greed, Floyd is based on dynamic programming and Bellman-Ford is based on discrete mathematics.

Selection of algorithm: Generally speaking, the short-circuit of single source is the shortest, if there is no negative weight edge, Dijkstra is used; if there is negative weight edge, SPFA is usually used, and Bellman-Ford is rarely used. The shortest of multiple sources, use Floyd.

Algorithm ideas

Simple Dijkstra

Suppose there are n points in the graph with subscripts from 1 to n. The distance of a point mentioned below refers to the distance between the point and the starting point (point 1).

The algorithm steps are as follows: a set S is used to store the point whose shortest distance has been determined.

  1. Initialization distance, d[1] = 0, d[I] = +∞. That is, the distance from the starting point is initialized to 0, while the distance from the remaining points is currently undetermined and is represented by positive infinity.

  2. cycle

    Each time from the points with known distance, select a point not in the S set with the shortest distance (this step can be optimized by using small root heap), traverse all the outsides of this point, and update the distance of the points connected by these outsides. And add the selected point to set S, because the shortest distance of the point is already determined.

  3. When all points are added to S, it means that the shortest distance of all points has been determined

Notice that just because we know the distance to a point, it doesn’t mean that the distance to that point is the shortest distance. Later in the cycle, it might take a shorter path to update.

Exercise: Acwing-849: Dijkstra finding the shortest circuit I

Problem solving (C++)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f; / / is infinite
int g[N][N]; // Dense graphs are stored by adjacency matrix
int d[N]; / / distance
int n, m;
bool visited[N];

int dijkstra(a) {
	d[1] = 0;
	/ / each time
	for(int i = 1; i <= n; i++) {
		// Find a point that is the smallest distance from the starting point
		int t = 0; // d[0] is not used, its value is always INF
		for(int j = 1; j <= n; j++) {
			if(!visited[j] && d[j] < d[t]) {
				t = j;
			}
		}
		if(t == 0) break; // If no point is found, break it
		// Find the point
		visited[t] = true; // add the set s
		// Update the distance of all other points
		for(int i = 1; i <= n; i++) { d[i] = min(d[i], d[t] + g[t][i]); }}if(d[n] == INF) return - 1;
	else return d[n];
}

int main(a) {
	/ / initialization
	memset(d, 0x3f.sizeof d);
	memset(g, 0x3f.sizeof g);
	scanf("%d%d", &n, &m);
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g[x][y] = min(g[x][y], z); // Only one edge with the least weight should be retained
	}
	printf("%d", dijkstra());
	return 0;
}
Copy the code

Problem Solving (Java)

import java.util.Arrays;
import java.util.Scanner;

/ * * *@Author yogurtzzz
 * @Date2021/6/25 9:01 ** dense graph, using adjacency matrix to store **/
public class Main {

	static final int INF = 0x3f3f3f3f;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n, m;
		n = scanner.nextInt();
		m = scanner.nextInt();
		int[][] g = new int[n + 1][n + 1]; // Graph adjacency matrix storage
		for(int i = 0; i < n + 1; i++) {
			for (int j = 0; j < n + 1; j++) g[i][j] = INF; // Initialize all distances to infinity
		}
		while(m-- > 0) {
			int x, y, z;
			x = scanner.nextInt();
			y = scanner.nextInt();
			z = scanner.nextInt();
			g[x][y] = Math.min(g[x][y], z); // To solve the heavy edge, keep the smallest distance of the edge
		}
		System.out.println(dijkstra(g, n));
	}

	/ * * *@paramThe adjacency matrix of g represents *@paramN Number of points ** */
	static int dijkstra(int[][] g, int n) {
		int[] distance = new int[n + 1];
		boolean[] visited = new boolean[n + 1]; // State variables
		Arrays.fill(distance, INF); // Initialize the distance to infinity
		distance[1] = 0; // The starting distance is 0
		// loop n times
		for (int i = 0; i < n; i++) {
			// Find the point with the smallest distance
			int min = 0;
			for(int j = 1; j <= n; j++) {
				if (!visited[j] && distance[j] < distance[min]) {
					min = j;
				}
			}
			if (min == 0) break; // all points are traversed
			// Find the point with the smallest distance
			visited[min] = true; // This is to solve the self-loop
			// Update the distance to enumerate all columns
			for(int j = 1; j <= n; j++) {
				// When there is an outedge, update its distance
				if (g[min][j] != INF) distance[j] = Math.min(distance[j], distance[min] + g[min][j]);
			}
		}
		if (distance[n] == INF) return -1;
		else returndistance[n]; }}Copy the code

Heap optimized version of Dijkstra

The heap can be hand-written (simulated with arrays) or used off-the-shelf (the STL in C++ provides priority_queue, and the JDK in Java provides PriorityQueue).

Exercise: ACwing-850: Dijkstra finding the shortest circuit II

Solution: handwriting heap (C++)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
// Sparse graph, using adjacency list to store, and choose heap optimization Dijkstra
const int N = 2e5;
const int INF = 0x3f3f3f3f;  / / is infinite

int h[N], e[N], w[N], ne[N], idx; // Adjacency list is stored. -1 indicates an empty node
int d[N]; / / distance
bool visited[N]; / / state
int n, m;

int hVal[N], hDis[N], hSize; // Array analog heap, hVal store node number, hDis store node distance
int ph[N], hp[N]; // Record the mapping between node subscripts in the heap and node numbers in the graph

// Swap two subscripts. Subscripts are subscripts in the heap
void heap_swap(int a, int b) {
	swap(hp[a], hp[b]); 
	swap(ph[hp[a]], ph[hp[b]]);
	swap(hVal[a], hVal[b]);
	swap(hDis[a], hDis[b]);
}

// Adjust upward, remember to adjust according to the distance hDis
void up(int pos) {
	while(pos / 2> =1 && hDis[pos / 2] > hDis[pos]) {
		heap_swap(pos, pos / 2);
		pos /= 2; // I missed this line.}}// Adjust downward, remember to adjust according to the distance hDis
void down(int pos) {
	int min = pos;
	if(2 * pos <= hSize && hDis[2 * pos] < hDis[min]) min = 2 * pos;
	if(2 * pos + 1 <= hSize && hDis[2 * pos + 1] < hDis[min]) min = 2 * pos + 1;
	if(min != pos) {
		heap_swap(pos, min);
		down(min);
	}
}

// Get and pop the top node of the heap
int pop(a) {
	if(hSize == 0) return 0; / / pile is empty
	int res = hVal[1]; // Node id
	heap_swap(1, hSize); // Swap the top and bottom of the heap
	hSize--; //
	down(1); / / adjust the heap
	return res;
}

// Insert a node into the heap, where x is the node number and dis is the distance from the node to the starting point
void insert_to_heap(int x, int dis) {
	// The subscript starts at 1
	hSize++;
	ph[x] = hSize;
	hp[hSize] = x;
	// Insert a number into the heap
	hVal[hSize] = x; // Record the node number
	hDis[hSize] = dis; // Record the node distance
	up(hSize); // Adjust upward
}

// Add an edge between x and y. The weight is z
void add(int x, int y, int z) {
    // Record the edge to the adjacency list
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

int dijkstra(a) {
	d[1] = 0; // Initialize, the starting point (point 1) distance is 0
	insert_to_heap(1.0); // Insert the starting point into the heap
	for(int i = 1; i <= n; i++) {
		// Determine one node at a time
		int t = pop(); // Obtain the point with the shortest distance. The node number ranges from 1 to n
		if(t == 0) break; // There are no elements in the heap, indicating that all nodes have been accessed, ending prematurely
		if(visited[t]) continue; // This point is already in set s
		visited[t] = true;
		// Update the distance of all edge points
		for(intj = h[t]; j ! =- 1; j = ne[j]) {
			int u = e[j]; // Node id
			int du = w[j]; / / side length
			if(d[u] > d[t] + w[j]) {
			    d[u] = d[t] + w[j];
			    insert_to_heap(u, d[u]); // Repeat points can also be inserted directly, no matter}}}if(d[n] == INF) return - 1;
	else return d[n];
}


int main(a) {
	memset(h, - 1.sizeof h); / / initialization
	memset(d, 0x3f.sizeof d); // The distance is initialized to INF
	memset(hVal, 0.sizeof hVal);
	memset(hDis, 0.sizeof hDis);
	scanf("%d%d", &n, &m);
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	printf("%d", dijkstra());
	return 0;
}
Copy the code

Using off-the-shelf heap (Java)

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/ * * *@Author yogurtzzz
 * @DateHeap-optimized version of Dijkstra's sparse graph, using adjacency lists to store **/
public class Main {
	
	static class Pair {
		int first;
		int second;

		Pair(int first, int second) {
			this.first = first;
			this.second = second; }}static Scanner scanner = new Scanner(System.in);
	
	static int INF = 0x3f3f3f3f;

	static final int N = 200000;

	static int[] h;
	static int[] e = new int[N], w = new int[N], ne = new int[N];// Graph adjacency list representation, array simulation linked list
	static int idx; // Used to assign list nodes
	
	public static void main(String[] args) {
		int n = readInt(), m = readInt();
		h = new int[n + 1];
		Arrays.fill(h, -1); // All adjacency lists are -1, indicating an empty linked list
		while(m-- > 0) {
			int x = readInt(), y = readInt(), z = readInt();
			add(x, y, z);
		}
		System.out.println(dijkstra(n));
	}
	
	private static int dijkstra(int n) {
		int[] distance = new int[n + 1];
		boolean[] visited = new boolean[n + 1];
		Arrays.fill(distance, INF);
		distance[1] = 0; // Initialize the starting distance
		/ / small root pile
		PriorityQueue<Pair> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.first));
		heap.offer(new Pair(0.1));  // Insert the starting point into the heap, first is the distance, second is the node number
		for(int i = 0; i < n; i++) {
			Pair p = heap.poll(); // Get the node with the smallest distance
			if (p == null) break; // There are no elements in the heap
			int nodeNo = p.second, nodeDis = p.first; // Get the number and distance of the object
			visited[nodeNo] = true; // Solve the self-loop
			for(intj = h[nodeNo]; j ! = -1; j = ne[j]) {
				// Get all outgoing edges of the node from the adjacency list
				int nextNodeNo = e[j];
				int nextNodeWeight = w[j];
				if (distance[nextNodeNo] > nodeDis + nextNodeWeight) {
					/ / update
					distance[nextNodeNo] = nodeDis + nextNodeWeight;
					// Insert into the heap
					heap.offer(newPair(distance[nextNodeNo], nextNodeNo)); }}}return distance[n] == INF ? -1 : distance[n];
	}
	
	// Add an edge
	private static void add(int x, int y, int z) {
		e[idx] = y;
		w[idx] = z;
		ne[idx] = h[x];
		h[x] = idx++;
	}

	private static int readInt(a) {
		returnscanner.nextInt(); }}Copy the code

Bellman-Ford

Algorithm ideas

Cycle n times

Each time, we iterate over all the edges of the graph. For each edge (a, b, w), update d[b] = min(d[b], d[a] + w)

You can define a class, or structure in C++, that stores a, b, and w. Indicates that there exists an edge point A pointing to point B with a weight of W). To iterate over all edges, just iterate over the entire structure array

The meaning of the number of cycles: assuming k cycles, it means the shortest distance from the starting point to each point through no more than K edges.

The algorithm can ensure that, after n cycles, all edges (a, b, w) satisfy d[b] <= d[a] + w. This inequality is called the triangle inequality. The update operation above is called the slack operation.

The algorithm is suitable for the case with negative edge weights.

Note: if there is a negative weight circuit, the shortest circuit does not necessarily exist. (Note that it may not exist). When the negative weight loop is on the path from point 1 to point N, the distance decreases every time you walk along the negative weight loop. Then you can go on indefinitely, and the distance from 1 to n becomes infinitesimal (minus infinity). At this point, the shortest distance from point 1 to point N does not exist. If the negative weight loop is not on the path from point 1 to point N, the shortest distance from 1 to n still exists.

This algorithm can determine whether there is a negative weight loop in the graph. If the iteration reaches the NTH time, it will still be updated, indicating that there is a shortest path, and there are n edges on the path, which requires N + 1 points. Since there are only N points in the figure, there must be two points in the n + 1 point, indicating that there is a loop on the path. It has a ring and is updated this time, indicating that the weight of the ring is negative (the update will only be performed if the total distance becomes smaller after the update).

However, to solve the negative weight loop, SPFA algorithm is usually used instead of Bellman-Ford algorithm, because the former has lower time complexity.

Because we loop n times, we iterate over all the edges (m edges) each time. Therefore, the time complexity of Bellman-Ford algorithm is O(n×m).

Practice: ACwing-853: The shortest circuit with edge limit

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

const int N = 510, M = 10010;
const int INF = 0x3f3f3f3f;
struct Edge
{
	int a, b, w;
} edge[M]; // Use the structure directly to store all edges

int n, m, k, d[N], tmp[N];

void bellman_ford(a) {
	memset(d, 0x3f.sizeof d);
	d[1] = 0; / / initialization
	for(int i = 0; i < k; i++) {
		memcpy(tmp, d, sizeof d); // Backup is required
		for(int j = 0; j < m; j++) {
			Edge e = edge[j];
			int a = e.a, b = e.b, w = e.w;
			if(tmp[a] == INF) continue;
			if(d[b] > tmp[a] + w) { // Use the previous d to calculate, in case there is a series case
				/ / updated[b] = tmp[a] + w; }}}if(d[n] == INF) printf("impossible");
	else printf("%d", d[n]);
}

int main(a) {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edge[i] = {x, y, z};
	}
	bellman_ford();
	return 0;
}
Copy the code

SPFA

In order to use SPFA algorithm, it must be required that there is no negative weight loop in the graph. SPFA can be used as long as there is no negative weight loop in the graph. The limitation of this algorithm is relatively small.

SPFA is actually an optimization of Bellman-Ford.

It optimizes this step: d[b] = min(d[b], d[a] + w)

We observe that d[b] is updated in the next cycle only when D [a] becomes smaller.

Consider using BFS for optimization. Use a queue to store nodes that are less distant.

(Very similar to Dijkstra)

Practice: ACwing-851: SpFA to find the shortest circuit

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;

// Use the adjacency list to store graphs
int h[N], e[N], w[N], ne[N], idx;

int d[N]; // Store the distance

int n, m;

void add(int x, int y, int z) {
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

void spef(a) {
	memset(d, 0x3f.sizeof d); // Initialize the distance
	d[1] = 0;
	queue<int> q;
	q.push(1);
	while(! q.empty()) {int t = q.front();
		q.pop();
		for(inti = h[t]; i ! =- 1; i = ne[i]) {
			// Update all outgoing edges
			int j = e[i];
			if(d[j] > d[t] + w[i]) { d[j] = d[t] + w[i]; q.push(j); }}}if(d[n] == INF) printf("impossible");
	else printf("%d", d[n]);
}

int main(a) {
	scanf("%d%d", &n, &m);
	memset(h, - 1.sizeof h); // Initialize the adjacency list, all empty linked lists
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	spef();
	return 0;
}
Copy the code

Advantages of SPFA: it can solve the problems without negative edge weights, and also can solve the problems with negative edge weights, and the efficiency is relatively high. However, bellman-Ford algorithm can only be used for the shortest path problem with no more than K edges.

Practice: ACwing-852: Finding negative rings with SPFA

The basic idea is to add a variable int CTN [N] to record the length of the edges to reach the ith point. If the number of edges to reach a point is greater than N, then there is a negative weight loop

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;

// Use the adjacency list to store graphs because you need outgoing edges
int h[N], e[N], w[N], ne[N], idx;

int d[N]; // Store the distance
int ctn[N];
bool visited[N];

int n, m;

void add(int x, int y, int z) {
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

void spef(a) {
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		q.push(i);
		visited[i] = true;
	}
	memset(d, 0x3f.sizeof d); // Initialize the distance
	d[1] = 0;
	while(! q.empty()) {int t = q.front();
		q.pop();
		visited[t] = false;
		for(inti = h[t]; i ! =- 1; i = ne[i]) {
			// Update all outgoing edges
			int j = e[i];
			if(d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				ctn[j] = ctn[t] + 1;
				if(ctn[j] >= n) {
					printf("Yes");
					return;
				}
				if(! visited[j]) q.push(j); }}}printf("No");
}

int main(a) {
	scanf("%d%d", &n, &m);
	memset(h, - 1.sizeof h); // Initialize the adjacency list, all empty linked lists
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	spef();
	return 0;
}
Copy the code

Floyd

To solve the shortest circuit problem of multi-source sink, it can also deal with the case of negative edge weight, but it cannot deal with the case of negative weight loop.

Use an adjacency matrix to store graphs. D [I][j] is initially used to store the graph, storing all edges

Algorithm idea: three layers of circulation

for(k = 1; k <= n; k++)

​ for(i = 1; i <= n; i++)

​ for(j = 1; j <= n; j++)

​ d[i,j] = min(d[i,j] , d[i,k] + d[k,j])

At the end of the loop, d[I][j] stores the shortest distance from point I to j.

The principle is based on dynamic programming (detailed principles will be explained in the following chapter of dynamic programming).

Its state is denoted as: d(k, I, j), the shortest distance from point I to point J through intermediate points 1 ~ k

Acwing-854: Finding the shortest circuit for Floyd

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;
int g[N][N]; // Adjacency matrix storage
int n, m, k;

void floyd(a) {
	for(int p = 1; p <= n; p++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(g[i][p] ! = INF && g[p][j] ! = INF) g[i][j] = min(g[i][j], g[i][p] + g[p][j]); }}}}int main(a) {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i == j) g[i][j] = 0;
			elseg[i][j] = INF; }}while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g[x][y] = min(g[x][y], z); // Handle heavy edges
	}
	floyd();
	while(k--) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(g[x][y] == INF) printf("impossible\n");
		else printf("%d\n", g[x][y]);
	}
	return 0;
}
Copy the code