文章目录

• 前言
• 一、Dijkstra是什么？
• 二、代码解读
• • 1.Dijkstra’s Pseudocode
  • 2.An example for 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

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