Dikstra algorithm can be used to find the weighted non-negative shortest path
The premise is that you can’t add negative weight and have direction
Principle:
(1) Find the node with the least weight.
(2) Check all the following unprocessed nodes of this node, calculate and add their weights respectively, and compare to get the node with the lowest weight.
(3) Repeat this process until it has been done for each node in the graph.
(4) Calculate the final path.
Like calculating the shortest path from the score to the piano
First of all, the score
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
As you can see, the smallest weight you have so far is the poster
Then the poster node is processed
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> Poster -> bass guitar | 30 |
Sheet music -> poster -> drum set | 35 |
You can see that the current unprocessed node minimum weight is vinyl
The vinyl record is being processed
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> Poster -> bass guitar | 30 |
Sheet music -> poster -> drum set | 35 |
Sheet music -> vinyl -> bass guitar | 20 |
Sheet music -> vinyl -> drum set | 25 |
Working with the vinyl record, the minimum path for the bass guitar and the drum set is now from the vinyl node so update the record
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> vinyl -> bass guitar | 20 |
Sheet music -> vinyl -> drum set | 25 |
Now the smallest weight of the unprocessed nodes is the bass guitar
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> vinyl -> bass guitar | 20 |
Sheet music -> vinyl -> drum set | 25 |
Music -> vinyl -> bass guitar -> piano | 40 |
The weight to get the end piano is 40, but there are still nodes that have not been processed, and now it is the minimum weight, so it is not finished, continue to deal with the drum
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> vinyl -> bass guitar | 20 |
Sheet music -> vinyl -> drum set | 25 |
Music -> vinyl -> bass guitar -> piano | 40 |
Music -> vinyl -> drum -> piano | 35 |
Get score -> vinyl -> drum -> piano less right to update the record
The path | The right to |
---|---|
Sheet music -> vinyl | 5 |
Sheet music -> Poster | 0 |
Sheet music -> vinyl -> bass guitar | 20 |
Sheet music -> vinyl -> drum set | 25 |
Music -> vinyl -> drum -> piano | 35 |
Therefore, according to the Dikstra algorithm, the minimum weight is 35, and the path is music -> vinyl records -> drum -> piano