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

This article mainly introduces python how to achieve the unauthorized shortest path related knowledge, the content is detailed and easy to understand, the operation is simple and fast, has a certain reference value, I believe that after reading this python how to achieve the unauthorized shortest path article will have a harvest, let's take a look.

Problem description

Problem: use a vertex s as an input parameter to find the shortest path from s to all other vertices.

Description: because it is an unauthorized graph, we can assign a value of 1 for each edge. Choose v3 as the starting point here.

Analysis of problems

At this point, you can immediately say that the shortest path from s to v3 is the path with a length of 0, marking this information.

Now start looking for a vertex with a distance of 1 from s. These vertices must be the vertices adjacent to s, and it is obvious that V1Magee V6 only needs one edge from s. Therefore, the vertex with a distance of 1 from s is v1 and V6.

Now start looking for the vertex with a distance of 2 from s. These vertices must be the vertices adjacent to v1rem V6 (the vertex with a distance of 1). It is found that the vertex adjacent to v1 is v2Jing v4, and the vertex adjacent to v6 is not (can not go back, no out edge). Therefore, the vertex with a distance of 2 from s is v2 and v4.

Finally, we examine the vertex adjacent to v2 and v4, that is, v5 and v7. Therefore, the vertex with a distance of 3 from s is v5 and v7.

This method of searching graphs is called breadth-first search (breadth-first search). Vertices are processed by layer, vertices close to the start point are processed first, and post-processing far away from the start point.

Pseudo code (processing node) void unweighted (Vertex s) {Queue Q = new Queue (); / / set the distance of each vertex to infinity for each Vertex v v.dist = INFINITY / / set the distance of the starting point to 0 s.dist = 0; / / queue the starting point as the start of the algorithm q.enqueue (s) / / continue to loop while (! q.isEmpty ()) {/ / get the outbound vertex Vertex v = q.dequeue () as long as the queue is not empty; / / A pair of vertices adjacent to v are processed by for each Vertex w adjacent to v if (w.dist = = INFINITY) {w.dist = v.dist + 1 W.path = v position / the last passing vertex of w is v / / after the operation is completed, the queue is used to analyze the vertices adjacent to w q.enqueue (w);}

The distance from s to the vertex is placed in the dv column, and the pv column is used to represent the last passing vertex of the vertex represented by the current row. The known column indicates that this vertex has been processed.

When initializing, the distance from the start point is set to 0, and all vertices are not know.

Combined with pseudo code for analysis:

[1] in the first cycle, v3 is out of the team (only one vertex per cycle)

[2] at the end of the first cycle, it is the data of "v3 out of the queue" in the above table, as follows

[3] at this point, the adjacent vertices of v3 are processed, so v3 changes from F to T (that is, known).

[4] the vertices adjacent to v3 are all processed, and the dv are all v3.

[5] and because the adjacent vertices of v1meme V6 have not been processed yet, the F of v1Magneol V6 cannot be changed into T yet.

Get the shortest path without authority

By observing the diagram, it can be found that there are two shortest paths with a length of 3.

[1] v3 = > v1 = > v2 = > v5

[2] v3 = > v1 = > v4 = > v7

We can find these two paths through the final situation of the data change table.

Note that the first line represents v1, and so on.

Take finding the path v3 = > v1 = > v2 = > v5 as an example, the process is as follows:

[1] find the vertex with a distance of 0, 0 in and only in the third row, so the first vertex is v3

[2] find the vertex whose distance is 1 and pv is v3, there are the first row and the sixth row, you must choose one here, the first row is selected here, so the second vertex is v1

[3] find the vertex whose distance is 2 and pv is v1. There are the second row and the fourth row. The second row is selected here, so the third vertex is v2.

[4] find a vertex with a distance of 3 and a pv of v2 with only the fifth row, so the fourth vertex is v5

[5] find a vertex with a distance of 4 and a pv of v5. No, end.

In fact, the above steps give the idea of finding out the algorithm of the shortest path without authority after the data processing of the vertices.

In fact, you can maintain some inter-vertex pointers to point to the next vertex, so you can do it recursively. From the starting point, each recursive distance from dv to the next layer is increased by 1, and an intermediate variable is used to store the vertices that pass through. Every time you call recursion, this intermediate variable is printed. In this way, you can get all the unauthorized shortest paths.

Here to get the shortest path of the pseudo-code is not given, the above analysis for your understanding and reference.

Code implementation

Paper will sleep shallow, never know the matter want to practice! I still think it's better to implement it once in code.

From queue import Queueclass Vertex: # vertex class def _ _ init__ (self,vid,outList): self.vid = vid# list of vertices pointed to by edge self.outList = outList#. It can also be understood that the adjacency table self.know = False# defaults to false self.dist = float ('inf') # s distance to that point, and defaults to infinity self.prev = the id of the last vertex The default is create vertex object v1=Vertex (1, [2pr 4]) v2=Vertex (2, [4pr 5]) v3=Vertex (3, [1je 6]) v4=Vertex (4, [3 pint 5 pint 7]) v5=Vertex (5, [7]) v6=Vertex (6, [6]) v7=Vertex (7, [6]) # create an array of length 8 to store vertices 0 index element does not store vlist = [False,v1,v2,v3,v4,v5,v6 V7] def unweighted (): # starting point is v3 vlist [3] .Dist = 0Q = Queue () q.put (vlist [3]) while (not q.empty ()): v = q.get () # return and delete the queue header element for w in v.outList: if (VList.Dist = float ('inf')): vlist [w ]. Dist = v.dist + 1 VList [w] .prev = v.vid q.put (VList [w]) unweighted () print ('v1. VList' ) print ('v2. 5) print ('v3. 5) print ('v3. 5) print ('v4. 5) print ('v5. 5) print ('v5. 5) print ('v6. 6) print V6.dist) print ('v7. Wow, 7. 9, 7. 5, 7. 5, 5, 7, 5, 5, 5, 5, 5, 5, 7, 7, 4, 5, 4, 5, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 and 4 respectively.) print ('v7.

Running result:

Consistent with the final situation of the data change table.

Here you may ask that the init function of the Vertex class clearly has a know member, why the program does not use the know member (after processing the node, the know of the node is set to Ture), because the judgment of if (vlist.Dist = = float ('inf')) is equivalent to judging whether the know of the node is Ture, because the distance of a known node is definitely not infinite.

Then use recursion to print out all the possible shortest paths and combine the following code with the above code.

Traj_list = [3] # v3 is the starting point directly plus def print_traj (dist): last = traj_list [- 1] print (traj_list,' the length of the path is:', VList [last] .Dist) temp_list = [] # Store the next option for i in range (1) Len (vlist): v = vlist [I] if ((v.dist==dist) and (v.prev==last)): temp_list.append (I) if (len (temp_list) = = 0): return# end # Recursive traj_list.append (I) print_traj (dist+1) with each option for i in temp_list:#i as vertex This is the end of the article traj_list.pop () print_traj (1) on "how to realize the shortest path without authority in python". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to achieve the shortest path without right in python". If you want to learn more knowledge, you are welcome to follow the industry information channel.

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.