Leetcode the shortest path of three (eight) charts per week

743. Network latency

Title Description

Yes n Network nodes , Marked as 1 To n.
Here's a list times, Indicates that the signal passes through Directed Edge transfer time . times[i] = (ui, vi, wi), among ui Is the source node ,vi It's the target node , wi Is a signal from the source node to the target node time .
Now? , From a node K Send a signal . How long does it take for all nodes to receive signals ？ If you can't make all nodes receive signals , return -1 .

Ideas

The problem is actually to find the node K The farthest distance to all other points , First, we need to find the nodes KK The shortest circuit to all other points , Then take the maximum value .

• The single source shortest path problem can be solved by Dijkstra Algorithm , Its core idea is greedy algorithm . The process is as follows ：
• First ,Dijkstra The algorithm needs to start from all the currently undetermined shortest path points , Find the point with the shortest distance from the source point x.
• secondly , Pass the point xx Update the shortest distance between all other points and the source point . For example, the current point A The shortest distance from the source point , A distance of 3; There is a A->B The directed side of , A weight of 1, Then go to the source first A Go again at B Point distance is 3 + 1 = 4, If originally from the source point to B The weight of the directed edge of is 5, Then we can update B The shortest distance to the source point is 4.
• When all other points are traversed , End of primary cycle , take xx Mark as having determined the shortest circuit . Enter the next cycle , Until all points are marked to determine the shortest circuit .

Code conversion ：

• First ,Dijkstra The algorithm needs to store each edge weight , Since the number of nodes in this question does not exceed 100100, So adjacency matrix is used in code graph[i][j] Store from point i point-to-point j Distance of . If no directed edge is given between two points , It is initialized to inf.
• The algorithm also needs to record the shortest distance from all points to the source point , The code uses dist[i] The array stores the source point to point i The shortest distance , The initial values are all set to inf. Because the source of this question is K, So the point distance is set to 0.
• secondly ,Dijkstra The algorithm needs to mark whether a node has determined the shortest path , Used in the code visit[i] Array storage , If the shortest distance has been determined , Then the value is true, Otherwise, it's worth false.

Code implementation

class Solution(object):
    def networkDelayTime(self, times, n, k):
        """ :type times: List[List[int]] :type n: int :type k: int :rtype: int """
        # The construction of adjacency matrix 
        graph = [[float('inf')] * n for _ in range(n)]       
        for x,y,w in times:
            graph[x-1][y-1] = w

        # The nearest distance matrix from the origin to each position 
        dist = [float('inf')] * n
        dist[k-1] = 0

        # visit flag Array 
        visit = [0]*n

        #dijstra Algorithm 
        for _ in range(n):
            x = -1
            # Find the point closest to the source point 
            for i,d in enumerate(dist):
                if (not visit[i]) and (d<dist[x] or x == -1):
                    x = i
            visit[x] = 1
            # to update dist Array 
            for i,d in enumerate(graph[x]):
                dist[i] = min(dist[i],dist[x]+d)
                # The point closest to the origin x The distance from the origin is dist[x]  Plus x Point distance i Dot weight  updated 
        ans = max(dist)
        return ans if ans != float('inf') else -1

result

847. The shortest path to access all nodes

Title Description

There is a reason for n Undirected connected graph composed of nodes , The nodes in the figure are displayed from 0 To n - 1 Number .
Give you an array graph It represents this graph . among ,graph[i] It's a list , By all and nodes i Directly connected nodes .
Return the length of the shortest path that can access all nodes . You can start and stop at any node , You can also revisit nodes many times , And you can reuse edges .

Ideas

• Because the problem requires us to find 「 The length of the shortest path to all nodes 」, And the length of each edge in the graph is 1, Therefore, we can consider using the breadth first search method to find the shortest path .
• In the conventional breadth first search , We will store the node number in the queue . For this question , The premise of the shortest path is 「 Visited all nodes 」, Therefore, in addition to recording the number of nodes , We also need to record the passing of each node . therefore , We use triples (u,mask,dist) Represents each element in the queue , among ：
  u Indicates the number of the node currently in ;mask Is a length of nn Binary number of , Indicates whether each node passes through . If mask Of the i Is it 1, Indicates the node i It's over , Otherwise, it means that the node i Not passed ;dist Indicates the path length up to the current node .
• thus , We use this triplet for breadth first search , Can solve the problem . At the beginning , We will all (i, 2^i, 0) Put in queue , Indicates that you can start at any node . In the process of searching , If... In the current triplet mask contain n individual 1（ namely mask=2^n−1）, Then we can return to dist As the answer .

details

• In order to ensure the correctness of the time complexity of breadth first search , That is, the same node u And the passing of nodes mask Was searched only once , We can use arrays or hash tables to record (u,mask) Whether it has been searched , Prevent invalid duplicate searches .
• bfs It must be better to arrive first , This common sense , Because of the water wave diffusion
• seen[v][mask_v] The record is running to v Node status is mask_v( Record the status by pressure , If a node runs past, let mask_v The corresponding binary bit is 1), and !seen[v][mask_v] It is about running to the current node v Status as mask_v Has it ever happened before , According to the nature 1, If it happened before , Then it must be better ( Not worse, to be exact ), Then you can use the previous one , Then the current situation can be ignored ( This also guarantees that there will be no looping )
• if (mask == (1 << n) - 1) {
  ans = dist;
  break;
  }
  Also according to the nature 1, If all the points have been run once , Then the running method to reach this state for the first time must be the best .

Code implementation

class Solution(object):
    def shortestPathLength(self, graph):
        """ :type graph: List[List[int]] :rtype: int """
        n = len(graph)
        que = deque((i,1<<i,0) for i in range(n))
        seen = {
    (i,1<<i) for i in range(n)}

        while(que):
            u,mask,dist = que.popleft()
            if mask == (1<<n)-1:
                return dist
                
            for v in graph[u]:
                mask_v = mask | (1<<v)
                if (v,mask_v) not in seen:
                    que.append((v,mask_v,dist+1))
                    seen.add((v,mask_v))               

result