Shulou(Shulou.com)06/03 Report--

How to use the Dijkstra algorithm, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Shortest path problem

Shortest path problem (Shortest Path Problems): given a network, the edge of the network has weights, find a path from a given starting point to a given end point to minimize the sum of edge weights on the path.

The shortest path problem is usually solved by Dijkstra algorithm.

Dijkstra algorithm

Dijkstra algorithm is a typical single-source shortest path algorithm, which is used to calculate the shortest path from one node to all other nodes. The main feature is that it expands layer by layer with the starting point as the center until it reaches the end point.

For example, the Dijkstra algorithm in the above figure is the process of constantly finding all the paths from the start node to the neighbor node, setting the initial distance to the shortest distance, and then constantly updating the shortest distance of the neighbor node until the shortest distance of the farthest node is solved.

The text description is not clear. Look at the motion picture below.

The vertices on the graph are divided into two sets: visited visited and unvisited node.

One point at a time from the visited, the extension rule is the smallest distance in the updatable point.

Let's take the picture above as an example.

First, the undirected graph is represented by adjacency matrix:

MAX = 9999 g = [[0,1,4,6], [MAX, 0, MAX, 2], [MAX, MAX, 0,1], [MAX, 0]]

The adjacency matrix g [0] [1] = 1 means that the distance from the first node to the second node is 1.

The purpose is to require the minimum path distance from the starting point 1 to other points.

N = 4 # 4 points # initialization visited visitd = [0] * (n) # record whether the point has been visited # the first point has been visited visitd [0] = 1 # distance from the source point to each point node set d = g [0] for i in range (2, n): # traversal d take out the position of the node with the lowest weight minWeigth = MAX for j in range (2) N): if d [j]

< minWeigth and visitd[j] == 0: minWeigth = d[j] k = j # 表示k是当前距1最短的点，同时标记k已经被找过 visitd[k] = 1 # 用该点进行松弛(relax) for j in range(2, n): if d[j] >

D [k] + g [k] [j] and visitd [j] = 0: d [j] = d [k] + g [k] [j] for i in range (1line n): print (d [I]) 1 45

At this point, the shortest distance from node 1 to the other three nodes is 1, 4, and 5.

The Dijkstra algorithm is applied to the unweighted graph, or the weight of all edges is equal, and the Dijkstra algorithm is equivalent to BFS search. "

Multi-point solution

In many cases, it is required to input a set of points, and then find a starting point to get the shortest path of the undirected graph.

Import math # suppose the number of vertices in the graph V = 6 # Mark array: the value of used [v] is False, which means that the vertices have not been accessed, in S, otherwise in U! Used = [False for _ in range (V)] # distance array: distance [I] represents the shortest distance from the source s to I, distance [s] = 0 distance = [float ('inf') for _ distance (V)] # cost [u] [v] represents the weight of the edge e = (UMagnev) If it does not exist, set to INF # cost connection table cost = [float ('inf') for _ in range (V)] for _ in range (V)] def dijkstra (s): distance [s] = 0 while True: # v is equivalent to a sentinel here, including the starting point s for unified processing! V =-1 # choose one of the vertices with the smallest distance for u in range (V): if not used [u] and (v =-1 or distance [u] < distance [v]): v = u if v =-1: # which means that all vertices are maintained in S! Break # adds the selected vertices to S while updating the distance used [v] = True # updates the distance from each vertex in U to the starting point s. The reason for updating the distance of vertices in U is that k is determined in the previous step as the vertex that finds the shortest path, so that k can be used to update the distance of other vertices; for example, the distance of (sforce v) may be greater than the distance of (sforce k) + (k force v). For u in range (V): distance [u] = min (distance [u], distance [v] + cost [v] [u]) for _ in range (9): v, u, w = list (map (int, input (). Split ()) cost [v] [u] = w cost [u] [v] = w s = int (input ('please enter a starting point:') dijkstra (s) print (distance)

Test case

0 1 1 0 2 2 0 3 3 1 7 1 5 9 2 4 4 3 4 5 3 5 6 458 Please enter a starting point: 0 [0, 1, 2, 3, 6, 9]

The 0 1 1 in the test case indicates that the distance from the first vertex to the second vertex is 1.

The time complexity of using adjacency tables in Dijkstra algorithm is. As a result, many use heaps to optimize or hash tables to optimize excess space.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.