Dijkstra简单介绍

文章目录


前言

大概介绍一下Dijkstra


一、Dijkstra是什么?

Dijkstra是为了搜索某节点到其它节点最小距离的算法

二、代码解读

1.Dijkstra’s Pseudocode

1 PQ = new PriorityQueue()
2 PQ.add(A, 0)
3 PQ.add(v, infinity) # (all nodes except A).
4
5 distTo = {} # map
6 distTo[A] = 0
7 distTo[v] = infinity # (all nodes except A).
8
9 while (not PQ.isEmpty()):
10 		popNode, popPriority = PQ.pop()
11
12 		for child in popNode.children:
13 			if PQ.contains(child):
14 			potentialDist = distTo[popNode] +
15 				edgeWeight(popNode, child)
16 			if potentialDist < distTo[child]:
17				 distTo.put(child, potentialDist)
18 					PQ.changePriority(child, potentialDist)

PQ represents an Empty PriorityQueue then we put A and all other nodes to the PQ, infinity means their minimum distance to A.
distTo stores the minimum distance to A from other nodes.

First, pop out A and check A’s children, edgeWeight means weight between popNode and child. If potentialDist is less than the current minimum distance. Update it by changing the value in PQ and also change the corresponding K-V in distTo.

2.An example for Dijkstra

Dijkstra简单介绍

1.Initial PQ

Node Distance
A 0

Then pop out A and update distance by visiting its children.
2.PQ after visiting A’s children

Node Distance
B 1
D 2
E 7

Then pop out B and update distance by visiting its children.
3.PQ after visiting B’s children

Node Distance
D 2
C 4
E 7

Then pop out D and update distance by visiting its children.
4.PQ after visiting D’s children

Node Distance
C 4
E 5

Then pop out C and update distance by visiting its children.

5.PQ after visiting C’s children

Node Distance
E 5
F 6
G 8

Then pop out E and update distance by visiting its children.
6.PQ after visiting E’s children

Node Distance
F 6
G 8

Then pop out F and update distance by visiting its children.
6.PQ after visiting F’s children

Node Distance
G 7

Then pop out G and update distance by visiting its children.
6.PQ after visiting G’s children

Node Distance

总结

End

上一篇:NowCoder088--寻找第k大


下一篇:go语言引入本地依赖包