Today, the 34th article in our algorithmic data structure series, we continue to talk about the shortest algorithm.

In the last article, we explained bellman-Ford algorithm and SPFA algorithm, among which SPFA algorithm is the one I often use, and almost no other short-circuit algorithm was used in the competition. But spFA also has its drawbacks, and we talked about its complexity before, where E is the number of edges. But sometimes the number of edges is so large that E is at most able to reach it, and that leads to a timeout, so we have to change the algorithm. The other algorithm we’re talking about here is Dijkstra.

Algorithm thought

In the last article, we once said that Bellman-Ford algorithm is a dynamic programming algorithm in essence. Our state is the shortest distance of each point, and our strategy is the feasible edge. Since we need to relax V-1 times at most, the overall algorithm complexity is very high. When we maintain points that can be relaxed with queues, we reduce the complexity to the SPFA algorithm.

Although Dijkstra algorithm and Bellman-Ford algorithm are the shortest circuit algorithm, but the core logic is not the same. The underlying logic of Dijkstra’s algorithm is greed, which can also be understood as the use of greedy algorithm in graph theory.

Dijstra, like Bellman-Ford, is a relaxation process. So we start off with all the points except s being infinite, and we’re going to have to go through this graph and relax those distances. The relaxation is to make these distances smaller. Suppose we have found the distance between two points u and v, and we call dis[u] the distance from u to s, and dis[v] the distance from v.

Suppose we have dis[u] < dis[v], that is, u is closer to s, then we are going to use a new point to search for the possibility of relaxation, which is more likely to get a better result, u or v? U, of course, so we choose u to do the new relaxation, and that’s the greedy algorithm. If you understand this layer, the whole idea of the algorithm is pretty much there.

Let’s tidy up our thoughts and look at the complete algorithm flow:

  1. We use an array dis to record the shortest distance from the source point S to other points, starting with dis[s] = 0 and setting the other values to infinity
  2. We select the point u with the smallest distance among the points we have never visited and mark it as visited
  3. If dis[v] < dis[u] + l[u] [v], dis[v]
  4. Repeat steps 2,3 above until all accessible points have been accessed

Well, there’s only two steps to the core, so that makes sense, right? I found a good GIF, you can compare the GIF according to the above process to deepen your understanding.


It’s not hard to write code based on the principle:

INF = sys.maxsize

edges = [[]] # adjacency list stores edges

dis = [] Record the distance from s to other points

visited = {} Record the points visited



while True:

    mini = INF

    u = 0

    flag = False

    Pass through the smallest distance of all unvisited points

    for i in range(V):

        if i not in visited and dis[i] < mini:

            mini, u = dis[i], i

            flag = True

            

    # Exit if there are no unaccessed points

    if not flag:

        break

        

 visited[u] = True

    

    for v, l in edges[u]:

        dis[v] = min(dis[v], dis[u] + l)

Copy the code

We already know that there are no counterexamples, but think about it a little bit. The main point is that each time we choose a point that is not visited to relax, is it possible that we relax a point that is already visited, and because it has already been relaxed, we can’t relax other points later?

Well, it’s impossible, because we pick the smallest unvisited point every time. Suppose that the current point is u, and we find a point v that has been visited, there cannot be dis[u] + L < dis[v], because dis[v] must be less than dis[u] for V to be visited before u. But that’s assuming that the length of each side can’t be negative.

Algorithm to optimize

Like Bellman-Ford, Dijkstra’s biggest problem is complexity. We choose one point at a time to relax, and when we do that we have to go through all the points, which is obviously very time consuming. The complexity should be, where E is the number of edges, each point in Dijkstra will relax only once, which means that each edge will be traversed at most once.

And if we look at it, we can see that the outside loop doesn’t matter, the inside loop is unnecessary, we’re just looking for a maximum value. It is perfectly possible to use data structures instead of circular queries, and to maintain maximum values we are already familiar with, using priority queues of course.

This code will be very simple with priority queues, again no more than ten lines, for the convenience of students debugging, I have posted the priority queue implementation code.

import heapq

import sys



# priority queue

class PriorityQueue:

  

    def __init__(self):

        self._queue = []

        self._index = 0



    def push(self, item, priority):

        We pass in two arguments, one is the array to store the elements, and the other is the element to store, which is a tuple.

        The value of priority is negative because the heap is sorted from small to large by default

        heapq.heappush(self._queue, (-priority, self._index, item))

        self._index += 1



    def pop(self):

        return heapq.heappop(self._queue)[- 1]





    def empty(self):

        return len(self._queue) == 0







que = PriorityQueue()



INF = sys.maxsize

edges = [[], [[2.7], [3.9], [6.14]], [[1.7], [3.10], [4.15]], [[1.9], [2.10], [6.2], [4.11]], [[3.11], [5.6]], [[4.6], [6.9]], [[3.2], [5.9]]] # adjacency list stores edges

dis = [sys.maxsize for _ in range(8)] Record the distance from s to other points

s = 1

que.push(s, 0)

dis[s] = 0

visited = {}



while not que.empty():

    u = que.pop()

    if u in visited:

        continue

    visited[u] = True

    for v, l in edges[u]:

        if v not in visited and dis[u] + l < dis[v]:

            dis[v] = dis[u] + l

            que.push(v, dis[v])



print(dis)

Copy the code

The main purpose of using Visited here is to prevent the generation of negative loops, so that the program will fall into an infinite loop. If it is confirmed that there is no negative edge in the program, there is no need to judge. Because the first one out of the queue must be better, there will not be a situation that will be updated later. If you don’t understand this point, it doesn’t matter to add judgment.

Finally, let’s look at the complexity. Each point is queued at most once, plus the adjustment time of the priority queue, the overall complexity is much faster than the previous complexity, which is very suitable for graphs with many edges and relatively few points. Sometimes when spFA is out of time, we choose Dijkstra.

This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).

Original link, ask a concern

– END –