python画图指定起点_python编程练习---有向加权图，最短路径（固定起点）

求从start到end的最短路径

涉及到无回环路径的情况(A-》B、B-》A)，可以使用dijkstra算法(狄克斯特拉)

算法步骤详解：

1、找出“最便宜”的节点，即可在最短时间内到达的节点(从start出发，最短距离的节点)

2、更新通过该节点，到其他邻居节点的最短距离

3、重复这个过程，直到对图中的每个几点都这样做了

4、计算最短路径

1、根据图片各节点之间的距离，建立数据关系

graph表示各节点可达节点的距离

graph = {}

graph["start"] = {}

graph["start"]["A"] = 5

graph["start"]["B"] = 2

graph["A"] = {}

graph["A"]["C"] = 4

graph["A"]["D"] = 2

graph["B"] = {}

graph["B"]["A"] = 1

graph["B"]["E"] = 6

graph["C"] = {}

graph["C"]["end"] = 2

graph["D"] = {}

graph["D"]["end"] = 1

graph["E"] = {}

graph["E"]["D"] = 1

graph["E"]["end"] = 4

graph["end"] = {}

2、建立一个数据结构，用来存储从start节点，到各个节点的距离，不知道距离的节点，先记做无穷大(math.inf)

infinity = math.inf

costs = {}

costs["A"] = 6

costs["B"] = 2

costs["C"] = infinity

costs["D"] = infinity

costs["E"] = infinity

costs["end"] = infinity

3、建立一个数据结构，用来存储从start节点，到各个节点最短距离时，该节点的父节点

parents = {}

parents["A"] = "start"

parents["B"] = "start"

parents["C"] = None

parents["D"] = None

parents["E"] = None

parents["F"] = None

根据节点图，初始化的3个数据结构已经创建完成

计算start到各个节点的最小距离，就可以按照算法步骤来完成

1、首先查找start节点出发可达的最小距离的节点返回该节点

#如果节点被检查过，则添加到processed中

processed = []

def find_lowest_cost_node(costs):

lowest_cost = infinity #未检查过的节点最小距离

lowest_cost_node = None #节点初始化

for node in costs: #遍历节点

cost = costs[node] #返回start到节点的距离

if cost < lowest_cost and node not in processed: #如果节点距离小于最小距离，并且该节点没有被检查过，那么设置最小距离为当前被检查的节点的最小距离，最小距离节点为当前检查的节点

lowest_cost = cost

lowest_cost_node = node

return lowest_cost_node #返回最小节点

2、计算从start节点，经过最小距离节点到最小距离节点的邻节点的距离，并更新相关数据结构。依次对剩余未检查的节点进行遍历

例如：start到B，最小距离为2，先检查B节点，然后计算start经过B到B的邻节点A、E的距离

start->B->A 的距离为2+1=3，小于start->A(6)，所以，需要更新costs中start到A的最小距离为3，parents中，A的父节点为B

#首先找到最小距离的节点

node= find_lowest_cost_node(costs)

#当节点不为空时

while node is not None:

cost = costs[node] #start到node的距离

neighbors = graph[node] #node的邻节点

for n in neighbors.keys(): #遍历邻节点

new_cost = cost + neighbors[n] #start经过node到邻节点的距离

if costs[n] > new_cost: #判断start经过node到邻节点的距离与start到邻节点的最小距离，如果小于就更新最小距离与父节点

costs[n] = new_cost

parents[n] = node

processed.append(node) #被检查的节点添加到数组中

node = find_lowest_cost_node(costs) #遍历

最终打印parents、costs，就可以知道从start到各个节点的最小距离以及最小距离的父节点

print(parents)

print(costs)

{'A': 'B', 'B': 'start', 'C': 'A', 'D': 'A', 'E': 'B', 'end': 'D'}

{'A': 3, 'B': 2, 'C': 7, 'D': 5, 'E': 8, 'end': 6}

从中可以看出start到end的最小距离为6，父节点关系：end->D->A->B->start(路径为：start-B-A-D-end)