The shortest path

directory

  • The shortest path

    • Dijkstra algorithm

      • Algorithm thought

      • The specific implementation

        • Adjacency matrix edition
        • The adjacency list version

      • The shortest path

        • Multiple shortest paths

      • Dijkstra+DFS

Shortest path problem:

Given any graph G (V, E), starting point S, ending point T, how to find the shortest path from S to T.

Common ways to solve shortest paths are

  • Dijkstra algorithm
  • Bellman – Ford algorithm
  • SPFA algorithm
  • Floyd algorithm

Dijkstra algorithm and its variants are summarized here.

Dijkstra algorithm

Algorithm thought

Dijkstra algorithm is used to solve the single-source shortest path problem, that is, given graph G and starting point S, the shortest distance from S to every other vertex can be obtained through the algorithm.

The basic idea of Dijkstra’s algorithm:

Set set S for graph G (V, E) to store the visited vertices, and then select the vertex (u) with the shortest distance from the starting point S from set V-S every time to access and join set S. Then, take vertex U as the intermediate point and optimize the shortest distance between the starting point S and all the vertices that can be reached from u. This operation is performed on n (n is the number of vertices) until set S contains all vertices.

Detailed strategy:

First set set S to hold the vertices already accessed, then perform the following two steps n times (number of vertices)

  1. Each time from the set V-s, select the vertex with the shortest distance from the starting point S (denoted by U), access and join the set S
  2. Let vertex u be the intermediate point, and optimize the shortest distance between all vertices V that can be reached from u

The specific implementation

There are two main issues to consider during implementation:

  • Implementation of set S
  • Implementation of the shortest distance from starting point S to vertex Vi (0<= I <= n-1)
  1. The set S can be implemented with a bool array vis[], that is, vis[I] == true indicates that vertex Vi has been accessed
  2. Let d[] represent the shortest distance from the starting point to vertex Vi. Initially, all vertices are assigned a large number except d[s] = 0 of the starting point S

The pseudocode is as follows:

void Dijkstra(G, d[], s) {initialize;for(loop n times) {u = the vertex label that minimizes d[u] and has not yet been accessed; Record Q is accessed;for(all vertices v reachable from u) {if(v is not accessed && using u as the intermediate point makes the shortest distance d[v] from s to V better) {optimize d[v]; }}}}Copy the code

Adjacency matrix edition

const int MAXV = 1000;	// Maximum number of vertices
const int INF = 1e9;		// INF large number

int n, G[MAXV][MAXV];		// n is the number of vertices, MAXV is the maximum number of vertices
int d[MAXV];						// The length of the shortest path from the starting point to each point
bool vis[MAXV] = {false};	// Whether it has been accessed

// s is the starting point
void Dijkstra(int s) {
		fill(d, d+MAXV, INF);	// The initialization distance is the maximum
  	d[s] = 0;
  	for(int i = 0; i < n; i++) {	// Repeat n times
      int u = - 1, MIN = INF;
      
      // Find the smallest d[] of the unvisited vertices
      for(int j = 0; j < n; j++) {
        if(vis[j] == false&& d[j] < MIN) { u = j; MIN = d[j]; }}if(u == - 1) return;	INF (d[u], INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]
      vis[u] = true;	// mark u as accessed
      for(int v = 0; v < n; v++) {
        // If v does not access && u can reach v && with u as the intermediate point can make d[v] better
        if(vis[v] == false&& G[u][v] ! = INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; }}}}Copy the code

Time complexity: outer loop O(V), inner loop O(V), enumeration V requires O(V), the total complexity is O(V*(V+V)) = O(V2).

The adjacency list version

struct Node {
  int v, dis;	// v is the target vertex, dis is the edge weight
};
vector<Node> Adj[MAXV];	// Graph G, Adj[u] contains all vertices that can be reached from vertex V
int n;	// n is the number of vertices
int d[MAXV];	// The length of the shortest path from the starting point to each point
bool vis[MAXV] = {false};

void Dijkstra(int s) {// s is the starting point
  fill(d, d+MAXV, INF);
  d[s] = 0;	// To itself is 0
  for(int i = 0; i < n; i++) {	// loop n times
    int u = - 1, MIN = INF;
    
    // Find the smallest d[] of the unvisited vertices
      for(int j = 0; j < n; j++) {
        if(vis[j] == false&& d[j] < MIN) { u = j; MIN = d[j]; }}if(u == - 1) return;	INF (d[u], INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]
      vis[u] = true;	// mark u as accessed
    
    // Different from adjacency matrix
    for(int j=0; j < Adj[u][j].size(a); j++) {int v = Adj[u][j].v;	// Get the vertex that u can reach directly
      // v is not accessed && reaching v with u is shorter than d[v]
      if(vis[v] == false && d[u] + Adj[u][j].dis < d[v]) {
        / / updated[v] = d[u] + Adj[u][j].dis; }}}}Copy the code

When they give you an undirected edge (bidirectional) instead of a directed edge, you just think of the undirected edge as two opposite directed edges.

The shortest path

We haven’t talked about how shortest paths are recorded yet, so let’s go back to pseudocode, and there’s a step like this, right

	for(all vertices v reachable from u) {if(v is not accessed && using u as the intermediate point makes the shortest distance d[v] from s to V better) {optimize d[v]; }}Copy the code

We will record this information at this point, that is, set a pre[] array so that pre[v] represents the number of the last vertex (precursor) on the shortest path from s to v, so that when the condition in the pseudocode is true, u is assigned to Pre [v], and it is recorded.

The pseudocode becomes:

For (all vertices v reachable from u) {if(v is not accessed && the shortest distance d[v] from s to v is better with u as the intermediate point) {optimize d[v]; Let v precede u}}Copy the code

Take the adjacency matrix as an example:

const int MAXV = 1000;	// Maximum number of vertices
const int INF = 1e9;		// INF large number

int n, G[MAXV][MAXV];		// n is the number of vertices, MAXV is the maximum number of vertices
int d[MAXV];						// The length of the shortest path from the starting point to each point
int pre[MAXV];	// Record the shortest path
bool vis[MAXV] = {false};	// Whether it has been accessed

// s is the starting point
void Dijkstra(int s) {
		fill(d, d+MAXV, INF);	// The initialization distance is the maximum
  	d[s] = 0;
  	for(int i = 0; i < n; i++) {	// Repeat n times
      int u = - 1, MIN = INF;
      
      // Find the smallest d[] of the unvisited vertices
      for(int j = 0; j < n; j++) {
        if(vis[j] == false&& d[j] < MIN) { u = j; MIN = d[j]; }}if(u == - 1) return;	INF (d[u], INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]
      vis[u] = true;	// mark u as accessed
      for(int v = 0; v < n; v++) {
        // If v does not access && u can reach v && with u as the intermediate point can make d[v] better
        if(vis[v] == false&& G[u][v] ! = INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; pre[v] = u;// record v's precursor is u}}}}// Output node
void DFS(int s, int v) {
  if(v == s) {	// We have recursed to the starting point s
    printf("%d\n", s);
    return;
  }
  DFS(s, pre[v]);			// access the vertex pre[v]
  printf("%d\n", v);	// Return from the deepest level to print the node number of each layer
}
Copy the code

Multiple shortest paths

We’ve learned Dijkstra and shortest paths at this point, but there’s usually more than one shortest path.

So when there are more than two shortest paths that can be reached, they give you a second ruler (the first ruler is distance) and ask you to choose the path with the best second ruler among all the shortest paths.

There are usually three ways:

  1. Add another edge weight to each edge (e.g. cost)
  2. Add a point weight to each point
  3. I’m just asking you how many shortest paths there are

In all three cases, you simply add an array to hold the new edge weights or point weights or the number of shortest paths, and then modify the step to optimize d[v].

For the above three questions, the solutions are as follows:

  1. Added edge weights. Take the newly added edge weight to represent the cost as an examplecost[u][v]Represents the cost from u->v, increment an arrayc[], so that the minimum cost from starting point S to vertex u is c[u], only when initializedc[s] = 0, the rest are INF (maximum distance). Then, ind[u] + G[u][v] < d[v]When the updated[v] andc[v]And whend[u] + G[u][v] == d[v] 且 c[u]+cost[u][v] < c[v]When the updatec[v].
for(int v = 0; v < n; v++) {
        // If v does not access && u can reach v && with u as the intermediate point can make d[v] better
        if(vis[v] == false&& G[u][v] ! = INF) {if(d[u] + G[u][v] < d[v]) {
            d[v] = d[u] + G[u][v];
            c[v] = c[u] + cost[u][v];
          }else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]) { c[v] = c[u] + cost[u][v]; }}}Copy the code
  1. Same as above, just switch to a weighted array.
  2. All you need to do is add an arraynum[], let the number of shortest paths from starting point S to vertex u benum[u], during initialization,num[s] = 1, and the rest are 0. whend[u] + G[u][v] < d[v], let num[v] inherit num[u]. And when thed[u] + G[u][v] == d[v]Add num[u] to num[v]. The code is as follows:
for(int v = 0; v < n; v++) {
        // If v does not access && u can reach v && with u as the intermediate point can make d[v] better
        if(vis[v] == false&& G[u][v] ! = INF) {if(d[u] + G[u][v] < d[v]) {
            d[v] = d[u] + G[u][v];
            num[v] = num[u];
          }else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]) {
            num[v] += num[u]; // Add num at the same shortest distance}}}Copy the code

Consolidate shortest paths through two topics:

PTA 1003 is a very worthwhile topic. Considering the three varieties of Dijkstra algorithm, I can be familiar with Dijkstra.

Dijkstra+DFS

The above problems are usually done using Dijkstra. However, it is easy to make mistakes when there are multiple rulers. Here is a more general and template method called Dijkstra+DFS.

In the algorithm, the pre array always maintains the optimal path, which obviously needs to determine when to update the precursor node pre[V] of each node V during the execution of Dijkstra’s algorithm. A simpler approach is to first record all shortest paths in Dijkstra’s algorithm (only the distance is considered) and then choose the path with the best second ruler from those paths.

  1. Use Dijkstra to record all shortest paths

We can use vector

pre[MAXV] to store the forecursors because we need to keep track of all shortest paths. For each node V, pre[v] is a vector of variable-length arrays containing all the shortest path precursors of node V.

Next consider the change in the pre array during d[v] update. First of all, if d[u]+G[u][v] < d[v], it means that using U as the intermediate point can make D [v] better. At this point, let the precursor node of V be U, and even if several nodes have been stored in pre[v] before, this node should be cleared, and then add U. Because it’s not an optimal path anymore.

if(d[u] + G[u][v] < d[v]) {
  d[v] = d[u] + G[u][v];
  pre[v].clear(a); pre[v].push(u);
}else if(d[u] + G[u][v] == d[v]) {
  pre[v].push(u);
}
Copy the code

Then we can write the complete code as follows:

vector<int> pre[MAXV];
// s is the starting point
void Dijkstra(int s) {
		fill(d, d+MAXV, INF);	// The initialization distance is the maximum
  	d[s] = 0;
  	for(int i = 0; i < n; i++) {	// Repeat n times
      int u = - 1, MIN = INF;
      
      // Find the smallest d[] of the unvisited vertices
      for(int j = 0; j < n; j++) {
        if(vis[j] == false&& d[j] < MIN) { u = j; MIN = d[j]; }}if(u == - 1) return;	INF (d[u], INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]), INF (d[u]
      vis[u] = true;	// mark u as accessed
      for(int v = 0; v < n; v++) {
        // If v does not access && u can reach v && with u as the intermediate point can make d[v] better
        if(vis[v] == false&& G[u][v] ! = INF) {if(d[u] + G[u][v] < d[v]) {
            d[v] = d[u] + G[u][v];
            pre[v].clear(a); pre[v].push_back(u);
          }else if(d[u] + G[u][v] == d[v]) {
            pre[v].push_back(u);
          }
        }
      }
    }  
}
Copy the code
  1. Traverse all shortest paths to find the path with the best second ruler.

Since each node may have multiple precursor nodes, the traversal process will form a recursive tree, and we can use DFS to find the optimal path. For tree traversal time, every time when you arrive at the leaf nodes will generate a complete shortest path, each get a path, you can calculate the second the value of the scale, make its and the second the optimal value of the scale, if better than the optimal value, the optimal value is updated, and use this path to cover the current optimal path.

Let’s think about how to implement this recursive function.

  • The optimal value optValue is the second ruler of the global variable
  • The array path that records the optimal path (stored in a vector)
  • Temporarily record the path of the DFS traversal to the leaf node tempPath (using vector storage)

Then consider the two components of recursive function: recursive boundary and recursive expression. If the node visited is leaf node (starting point ST), then it indicates that the recursive boundary has been reached. At this time, tempPath stores a path and compares the value of the second ruler with optValue.

TempPath is generated during recursion. Just add v to the end of tempPath when accessing the current node V, and iterate pre[v] for recursion. After traversing all nodes of Pre [V], pop v at the end of tempPath.

int optValue;
vector<int> pre[MAXV];
vector<int> tempPath, path;
int st;	// start node

void DFS(int v) {
  if(st == v) {
    // we recurse to the starting node
    tempPath.push(v);
    intvalue; Calculate the value of the tempPath pathif(value优于optValue) {
      optValue = value;
      path = tempPath;
    }
    tempPath.pop_back(a);// Pop out the new node
    return;
  }else {
    tempPath.push_back(v);	// Add the current access node to the end of the temporary path tempPath
    for(int i = 0; i < pre[v].size(a); i++) {DFS(pre[v][i]);
    }
    tempPath.pop_back();
  }
}
Copy the code

When we encounter point weights or edge weights, we only need to modify the process of calculating value.

Note, however, that the nodes of the path stored in tempPath are in reverse order, so the nodes need to be accessed backwards.

// Sum of edge weights
int value = 0;
for(int i = tempPath.size() - 1; i > 0; i--) {
  int id = tempPath[i], idNext = tempPath[i- 1];
  value += V[id][nextId];
}

// Sum of weights of points
int value = 0;
for(int i = tempPath.size() - 1; i > 0; i--) {
  int id = tempPath[i];
  value += W[id];
}
Copy the code

If you need to record the number of shortest paths, you can also increase this global variable by 1 every time a leaf node is reached during DFS.

PTA 1030, which uses the idea of Dijkstra + DFS, can be used for reference.

It can be combined with the previous PTA 1003, and basically Dijkstra has no problems.

But the disadvantage of DIjkstra was that it was very weak when it came to negative weights, so a new algorithm emerged at this time.