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

This article introduces the relevant knowledge of "Dijkstra's single-source shortest path algorithm". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

single source shortest path problem

Given a weighted digraph G=(V,E,W), the weight w of each edge is nonnegative, denoting the distance between two vertices.

Source point s∈ V.

Find the shortest path from s to each other vertex.

As shown above, taking 1 as the source point, calculate the shortest distance to each of the remaining vertices (I've redlined them). The final solution is listed below:

Source: 1

1->6->2 : short[2] = 5

1->6->2->3 : short[3] = 12

1->6->4 : short[4] = 9

1->6->5 : short[5] = 4

1->6v : short[6] = 3

Dijkstra algorithm related concepts

S set: x ∈S when the shortest path from s to x (x ∈V) is found. When all vertices are in the S set, the algorithm ends.

Initial: S={s}, algorithm ends when S= V.

Shortest path from s to u relative to S: refers to the shortest path from s to u that passes through only the vertices in S.

dist[u]: shortest path length from s to u relative to S

short[u]: Length of the shortest path from s to u (algorithm final solution)

dist[u] ≥ short[u]

Dijkstra algorithm uses greedy algorithm mode, the algorithm process is to calculate dist[u], continuously expand S set, while dist[u] will continue to optimize and improve, until dist[u] = short[u], and put it into S, when all vertices are put into S set, the algorithm ends.

algorithm design idea

Input: weighted directed graph G=(V,E,W)

V={1,2,…,n}, s=1

Output: shortest path from s to each vertex

Initial S={1}

For u ∈V-S, compute the shortest path from 1 to u with respect to S of length dist[u]

Select the vertex with the smallest dist value in V-S and add S.

Continue this process until S= V.

examples

Input: G=(V,E,W), Source 1

V={1,2,3,4,5,6}

When vertex 6 is placed into the S set, the shortest distance from vertex 6 may be updated optimally, because the idea of the algorithm is "greedy," I want whoever is shorter! For example, 1->6->2 is shorter than 1->2, so dist[2] is updated to 5. In technical terms, this "updating" process is called relaxation, and the same applies to other points. Then find the vertex (number 5) of the shortest path from dist[u] and put it in the S set.

S={1,6}

dist[1] = 0

dist[6] = 3

dist[2] = 5

dist[4] = 9

dist[5] = 4

dist[3] = ∞

S={1,6,5,2}

dist[1] = 0

dist[6] = 3

dist[5] = 4

dist[2] = 5

dist[4] = 9

dist[3] = 12

S={1,6,5,2,4,3}

dist[1] = 0

dist[6] = 3

dist[5] = 4

dist[2] = 5

dist[4] = 9

dist[3] = 12

When all the vertices in the directed graph are in the S set, the algorithm ends, and the value of dist[u] at this time is actually the final solution short[u] we found initially, so at the end of the algorithm, dist[u]=short[u], we get the final solution.

"Dijkstra single source shortest path algorithm is what" content is introduced here, thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the website. Xiaobian will output more high-quality practical articles for everyone!

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.