把上述的解法封装了一下,然后加入“途经”其他节点的功能。
带权重的最优路径解法是现在用的许多导航地图算法的基础,所以还是很有必要研究一下的。
bestway(s,e,a,b)函数中,s代表起始点,e代表终点,a和b代表途径点(可选)。
- #coding:utf-8
- '''题目要求:起点(0),终点(9),找出权重最小的路径即为最优路径'''
- weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
- 1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
- 2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
- 3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
- 4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
- 5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
- 6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
- 7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
- 8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
- 9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
- 10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
- 11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
- dic = {}
- def dp(x,y):
- if (x,y) not in dic:
- dic[(x,y)] = [weight[x][y], [x,y]]
- else:
- for ea in dic:
- a,b = ea
- if a == x:
- for ch in dic:
- c,d = ch
- if b==c and d==y:
- if dic[(x,y)][0] > dic[(a,b)][0] + dic[(c,d)][0]:
- dic[(x,y)][0] = dic[(a,b)][0] + dic[(c,d)][0]
- dic[(x,y)][1] = dic[(a,b)][1] + dic[(c,d)][1]
- #initiate:
- for i in range(12):
- for j in range(12):
- if i != j:
- dp(i,j)
- def find(s,e):
- global dic
- record = dic[(s,e)][0]
- while True:
- for i in range(12):
- for j in range(12):
- if i != j:
- dp(i,j)
- if record == dic[(s,e)][0]:
- return dic[(s,e)]
- else:
- record = dic[(s,e)][0]
- def bestway(s,e,a=None,b=None):
- if not b:
- if not a:
- return find(s,e)
- else:
- result1 = find(s,a)
- result2 = find(a,e)
- return [result1[0]+result2[0], result1[1]+result2[1]]
- else:
- result1 = find(s,a)
- result2 = find(a,b)
- result3 = find(b,e)
- return [result1[0]+result2[0]+result3[0], result1[1]+result2[1]+result3[1]]
- print (bestway(0,9,7,3))
复制代码
输出:
[17, [0, 1, 1, 7, 7, 8, 8, 3, 3, 6, 6, 9]]
[Finished in 0.1s] |