Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "what are the ways to solve the shortest path of Python". The editor shows you the operation process through an actual case, which is simple, fast and practical. I hope this article "what are the ways to solve the shortest path of Python" can help you solve the problem.

Pre-knowledge

Graphs can be roughly divided into directed graphs and undirected graphs. The edges in the graph have positive weights and some negative weights.

Some have multiple roads between two points, and some even have self-loops (it can be said to be grey and flexible).

The data structures that can be used to create a diagram are:

Cross linked list, adjacency multiple table, adjacency matrix, edge set array, adjacency table

The first two problem solving methods of this blog use adjacency table, and the last one uses adjacency matrix.

Everyone can choose according to their own preferences, but the thinking is still the same.

If you are not familiar with the shortest path, I recommend you to take a look at this video of the UP master. I feel that the thief good portal is ready.

Cross list: a linked storage structure for directed graph storage, which can be regarded as a linked list obtained by combining the adjacency table and the inverse adjacency table of a directed graph. Using cross linked list to store directed graph can achieve efficient access effect. At the same time, the readability of the code will be improved.

Adjacency multitable: adjacency multitable is a storage method of undirected graph. The adjacency multiple table is an improvement of the adjacency list, which stores two vertices of the edge in the edge table node, and all the edges attached to the same vertex are connected in the same linked list. Because each edge is attached to two vertices, each edge table node is linked in two linked lists at the same time.

Adjacency matrix: a matrix that represents the adjacency relationship between vertices (personal feeling is also the simplest, but very unsuitable for sparse graphs). The logical structure is divided into two parts: v and E sets, where V is the vertex and E is the edge. Therefore, an one-dimensional array is used to store all the vertex data in the graph, and a two-dimensional array is used to store the data of the relationship between vertices (edges or arcs). This two-dimensional array is called adjacency matrix. The adjacency matrix is divided into directed graph adjacency matrix and undirected graph adjacency matrix.

Edge set array: edge set array (edgeset array) is a representation of a graph that uses an one-dimensional array to store all edges in a graph. The number of elements in the array should be greater than or equal to the number of edges in the graph, and each element is used to store the starting point and end point of an edge (for an undirected graph, any end point of the edge can be selected as the starting point or end point) and weight (if any). The order of the edges in the array can be arranged arbitrarily or according to specific requirements.

Exercise [single source shortest path & Dijstra] unblocked project

Problem description

Problem Description

After carrying out the smooth flow project for many years, a certain province has finally built many roads. But it's not good to have too many roads, every time you have to go from one town to another.

There are many road options to choose from, and some travel much shorter distances than others. This bothers pedestrians.

Now that you know the starting point and the end point, please calculate the minimum distance to walk from the starting point to the end point.

Input

This topic contains multiple sets of data, please deal with it until the end of the file.

The first row of each set of data contains two positive integers N and M (0

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.