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