This article is really about how to solve the shortest path problem.

In fact, the shortest path problem, we all unconsciously use in life. For example, when we are on the Internet, Internet transmission uses various packet routing methods. These routing algorithms work behind the scenes.

There are also pathfinding operations for graph algorithms, such as making game characters automatically find their way in games.

In fact, finding the shortest path is generally an important subroutine of other non-graph algorithms.

Let’s start with the shortest path problem:

The shortest path problem can be divided into the following forms. For example, to find shortest paths in directed and undirected graphs, the most important difference between the two is the starting point and the destination.

This problem can take many forms, such as the unique problem of the source node of the shortest path from one node to all other nodes, the one-to-one problem of the shortest path from one node to another, and the unique problem of the destination node of the shortest path from all other nodes to one node, There is also the problem of pair-wise combinations of all nodes in the shortest path from all nodes to other nodes.

So before we get into the body of the paper, let’s talk about relaxation and incremental improvement, and I’m not going to give you any more examples, but it’s just a way of doing it, and it’s a way of doing it by incremental approach to get the best solution for the problem.

Then take a look at this code:

Inf = float('inf') def relax(W, u, v, D, P): D = d.et (u, inf) + W[u][v] if D < d.et (v, inf): D[v], P[v] = d, u return TrueCopy the code

A dictionary that represents a graph as a dictionary and stores distance estimates in dictionary D. P is the leading node dictionary. Leading Pointers form the shortest path tree. You then decompose the relaxation technique using relax in common code. Any item that doesn’t exist in D can be considered infinite. They are also initialized to infinity in the main algorithm.

In this code, we use u to see if we can shorten the path, thereby improving the known shortest path to v. If it’s not the shortest path, ignore it. If it’s a shortest path, remember which nodes it went through.

And then let’s look at the first more formal algorithm, bellman-Ford. This algorithm is suitable for single source shortest path algorithm of any directed or undirected graph. If the graph contains negative loops, the algorithm outputs the information and then abandons the search.

Def bellman_ford(G, s): D, P = dict(s=0), dict() for RND in G: changed = False for u in G: for v in G[u]: if relax(G, u, v, D, P): changed = True if not changed: break else: raise ValueError('negative cycle') return D, PCopy the code

This algorithm includes charges to check changes, so multiple iterations are not required and the program can be terminated in advance. Ha can detect the presence of negative loops by determining whether extra iterations make a difference.

Then we look at a weight diagram:

The weight diagram is rewritten as a dictionary of dictionaries, which can be expressed as follows:

a, b, c, d, e, f, g, h = range(8)
G = {
    a: {b: 2, c: 1, d: 3, e: 9, f: 4},
    b: {c: 4, e: 3},
    c: {d: 8},
    d: {e: 7},
    e: {f: 5},
    f: {c: 2, g: 2, h: 2},
    g: {f: 1, h: 6},
    h: {f: 9, g: 8}
}
Copy the code

A concrete implementation of the algorithm, using the debugger, can add two print commands to show the edge of the relaxation operation and the value assigned to D.

If tested several times, it will be found that the distance estimates of G, H, and F keep suggesting, and in the eighth round there is still a decrease of one, which indicates the existence of a negative cycle.

The solution is to remove the (f, G) edge with del G[f][G]. So we don’t have negative cycles.

Then we add a constraint to the shortest path problem of single-source DAG graph, the ring can have, but the edge weight cannot be negative.

Then we introduce this Dijkstra algorithm, which is very similar in structure to Prim, and uses priority queues for traversal. In Dijkstra, priority is distance estimation. Then we look at the specific algorithm implementation:

From heapq import heappush, heappop def Dijkstra (G, s): D, P, Q, s = {s: 0}, {}, [(0, s)], set() while Q: _, u = heappop(Q) if u in S: continue S.add(u) for v in G[u]: relax(G, u, v, D, P) heappush(Q, (D[v], v)) return D, PCopy the code

The running time of this algorithm is Q((m+n) LGN), where m is the number of edges and n is the number of nodes.

Dijkstra algorithm is closely related to the breadth first search (BFS) algorithm. We can consider the case where the lower weight is a positive integer and replace an edge with w-1 unauthorized edges to form a path consisting of virtual nodes, as shown in the following figure:

BFS will always find the right answer, but it will become inefficient. At this time, we will find that BFS solves the problem in a similar way to Dijkstra algorithm: Huawei’s time on each edge is proportional to the edge weight, so it will reach each node in sequence from the starting node according to the distance.

And then the many-to-many problem:

Johnson algorithm is introduced here. The algorithm motivation is actually very simple. It solves the shortest path problem between all node pairs of sparse graph matrix, and Dijkstra algorithm is used when all nodes are identical. But Dijkstra doesn’t allow negative edge weights. For single-source shortest path problems, there is no other way to use Bellman-Ford algorithm.

And then we can imagine that we add a new node, s, whose edge weight to all the existing nodes is 0. And then we run Bellman-Ford for the case starting from S. This will calculate the distance from S to each node in the graph. Let’s call it h of v. And then we can adjust the weights of the edges with h. It can be defined as follows: w'(u, v) = W (u, v) + h(u) -h (v).

This definition ensures that the new weights are non-negative. And then you don’t introduce any new distractions.

Then Dijkstra algorithm is used to find the shortest path, and then reverse all the path lengths. The specific Johnson algorithm is as follows:

From copy import deepcopy def Johnson (G): G = deepcopy(G) s = object() G[s] = {v: 0 for v in G} h, _ = bellman_ford(G, s) del G[s] for u in G: for v in G[u]: G[u][v] += h[u] - h[v] D, P = dict(), dict() for u in G: D[u], P[u] = dijkstra(G, u) for v in G: D[u][v] += h[v] - h[u] return D, PCopy the code

Johnson’s algorithm is also pretty efficient, but it runs n times longer than Dijkstra’s algorithm.

Then we move on to the next problem, which is the method to find the shortest distance between all pairs of nodes:

The name of the algorithm is floyd-Warshall. It’s based on dynamic programming, and Dijkstra’s algorithm is based on dynamic programming.

Floyd-warshall is based on cache recursive decomposition, and the implementation process is generally iterative.

We need to find a set of recursively related subproblems.

We randomly sort the nodes and limit the number of intermediate nodes allowed to form the shortest path, the first K.

Here, three parameters are directly used to parameterize the sub-problem:

  1. Starting node
  2. Termination of the node
  3. Maximum number of nodes allowed to pass through

Then let the length of the shortest path from node U to node V be d(u, v, k) :

D (u, v, k) = min (d (u, v, k – 1), d (u, k, k – 1) + d (k, v, k – 1)).

This is the same as the knapsack problem, where you have to consider whether or not you want to include node K. No, it’s d(u, v, k-1). Include the shortest path d(u, k, k-1) to k and the shortest path d(k, v, k-1) out of k.

Then look at the code below:

Def rec_floyd_warshall(G): @memo def d(u, v, k): if k == 0: return G[u][k] return min(d(u, v, k-1), d(u, k, k-1) + d(k, v, k-1)) return {(u, v): D (u, v, len(G)) for u in G for v in G} # cache = dict() @wraps(func) def wrap(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrapCopy the code

Then we can try the iterative version:

Three arguments, three for loops. Let’s go straight to the code:

Def floyd-Warshall (G): D = deepcopy(G) for k in G: for u in G: for v in G D[u][v] = min(D[u][v], D[u][k] + D[k][v]) return DCopy the code

D is the current distance graph, and the previous distance graph is C. After conversion with only one distance map, the formula is as follows:

D[u][V] = min(D[u][V], C[u][k] + C[k][V]).

Transform as follows:

D[u][V] = min(D[u][V], D[u][k] + D[k][V]).

If a P matrix is added, P[u][v] will be replaced by P[k][v]. The code becomes:

Def floyd-warshall (G): D, P = deepcopy(G), dict() for u in G: for v in G: if u == v or G[u][v] == inf: P[u, v] = None else: P[u, v] = u for k in G: for u in G: for v in G: shortcut = D[u][k] + D[k][v] if shortcut < D[u][v]: D[u][v] = shortcut P[u, v] = P[k, v] return D, PCopy the code

This should be shortcut < D[u][v], not shortcut <= D[u][v], because in some cases the last step is D[v][v], which would result in P[u, v] = None.

Then on to the next question, the “halfway question” :

The solution to Dijkstra’s algorithm problem, if the nodes are S and T, will spread out on the graph from S to T. But if you start from the beginning and end at the same time, you can do a lot less work. The concrete is abstracted out like the figure below:

So if you modify it a little bit, you can turn it into a bidirectional version of Dijkstra’s algorithm. Can be a subsolution generator that lets us extract as many subsolutions as possible.

In this case, you must ignore the distance table and rely only on the distance values stored in the priority queue. Here is the sample code:

# Dijkstra algorithm as solution generator implementation from Heapq import Heappush, heappop def idijkstra(G, s): Q, s = [(0, s)], set() while Q: d, u = heappop(Q) if u in S: continue S.add(u) yield u, d for v in G[u]: heappush(Q, (d+G[u][v], v))Copy the code

No lead node information is introduced, but the solution can be extended by adding lead nodes to the heap tuple. To get the distance table, simply call dict(idijkstra(G, s)).

However, starting from both nodes at the same time, you may encounter the following problems:

The node that meets for the first time (highlighted node) is not necessarily on the shortest path (highlighted edge).

In fact, this problem only needs to be limited to the termination condition, just to see how far they have traveled, is the latest distance, this can not be reduced. The combination of the two is at least equal to the best path we have found so far, so it is impossible to find a better solution.

If G is an undirected graph and any node u satisfies G[u][u] = 0, the following code can be used:

From itertools import cycle def bidir_dijkstra(G, s, t): Ds, Dt = dict(), dict() forw, back = idijkstra(G, s), idijkstra(G, t) dirs = (Ds, Dt, forw), (Dt, Ds, back) try: for D, other, step in cycle(dirs): v, d = next(step) D[v] = d if v in other: break except StopAsyncIteration: return inf m = inf for u in Ds: for v in G[u]: if not v in Dt: continue m = min(m, Ds[u] + G[u][v] + Dt[v]) return mCopy the code

Of course, you can easily extend this code.

Next, we will introduce A* algorithm:

If we really know which edge is closer to the target, we can solve the problem with greedy algorithms. Move directly along the shortest path, ignoring other side routes.

The A* algorithm is A bit like the concept of heuristic search in artificial intelligence. Rather than blindly searching like DFS and BFS. It’s not like Dijkstra’s algorithm has no idea what’s going to happen.

Because A star adds A potential function, or you could call it A heuristic h of v.

Like the Johnson algorithm introduced above, we can define the modified edge weights:

w'(u, v) = w(u, v) – h(u) + h(v)

And then you see, after this adjustment, we can reward the right side and punish the wrong side. Then I added heuristic yams to the weights of the edges. The algorithm will develop in a direction that causes the remaining distance to fall.

The A* algorithm is equivalent to Dijkstra’s algorithm for the modified graph. If h works, the algorithm is correct.

H (s) is a constant, so we just add h(v) to the queue of existing priorities. This sum is our best estimate for going from s to T. If w prime of u, v works, then h of v will also be a lower bound on d of v, t.

Then this just gives the code directly, which calls the idijkstra function of the above code:

# A* from heapq import HEappop INF = float(' INF ') def a_star(G, s, t, h): P, Q = dict(), [(h(s), None, s)] while Q: d, p, u = heappop(Q) if u in P: continue P[u] = p if u == t: return d - h(t), P for v in G[u]: w = G[u][v] - h(u) + h(v) heappush(Q, (d + w, u, v)) return inf, NoneCopy the code

The advantage of the A* algorithm is the heuristic function, and the exact heuristic function depends on the problem to be solved.

In addition, the A* algorithm can also search the solution space. Can solve the Rubik’s cube problem or word ladder problem. Here’s the latter question.

The word ladder is built from the first starting word, such as lead, and then ends with another word, such as gold. Each step of the ladder is built using actual words, moving from one word to the next and changing only one letter. One solution to this problem, for example, would be to load and goad to lead and gold. If each word is seen as a node, we can add edges. It may not be necessary to do this, but assuming so, you can make the following code:

# aranez from string import ascii_letters as chars def variants(aranez, words): wasl = list(wd) for i, c in enumerate(wasl): for oc in chars: if c == oc: continue wasl[i] = oc ow = ''.join(wasl) if ow in words: yield ow words[i] = c class WordSpace: def __init__(self, words): self.words = words self.M = dict() def __getitem__(self, wd): if wd not in self.M: self.M[wd] = dict.fromkeys(self.variants(wd, self.words), 1) return self.M[wd] def heuristic(self, u, v): return sum(a! =b for a, b in zip(u, v)) def ladder(self, s, t, h=None): if h is None: def h(v): return self.heuristic(v, t) _, p = a_star(self, s, t, h) if p is None: return [s, None, t] u, p = t, [] while u is not None: p.append(u) u = P[u] p.reverse() return pCopy the code

WordSpace can be used as a weighted graph, in conjunction with a_star. The heuristic here simply counts the different character digits of the word. G is the object of WordSpace, G[‘lead’] is the dictionary, and other words are key values. The weights of the edges are 1.

That’s about it.

A* algorithms are usually covered in artificial intelligence books. Other algorithms can also be found in general algorithm books.

When designing new algorithms, such as the bidirectional version of Dijkstra’s algorithm combined with the heuristic of A*, there are likely to be pitfalls that make the algorithm ineffective.

The above. Thank you for your attention.

Today the beginning of winter, I wish you a happy winter, all the unhappy with the past autumn has passed. The new season is coming, I hope you all have a good mood.

It’s cold. Keep warm.