Python动态规划算法练习之最短路径

本程序体现了程序=数据结构+算法的最佳结合。采用动态规划求出从A点到G点的最短距离是11。
图：

def shortest_path(node):
    """node:节点,是一个元组,包含了所连接的其它点,
      如,f点,它的内容是((d,4),(e,2)),取出f点到d点的式子是:
      f[0][1]
      """
    if node!=tuple():
        dis = []
        for n in node:
            d = shortest_path(n[0]) + n[1]
            dis.append(d)
        return min(dis)
    else:
        return 0

# 设计的数据结构是用元组表示一个结点，而不是邻接矩形或邻接链表。
# 图1数据
##a = tuple()           # 起点是空元组
##b = ((a,2),)          # b点到a点的距离是2
##c = ((a,4),)
##d = ((b,2),(c,1))     # d点到b点的距离是2,到c点的距离是1
##e = ((b,3),(c,2))
##f = ((d,4),(e,2))

# 图2数据
a = tuple()

b = ((a,6),)                # 表示ab的长度是6
c = ((a,3),)                # 表示ac的长度是3
d = ((a,8),)

e = ((b,6),(c,5))           # 表示be的长度是5,ce的长度是5
f = ((c,3),(d,4))

g = ((e,6),(f,5))

print(shortest_path(g))

python数据结构与算法动态规划最短路径采用元组这种数据结构我认为还是非常容易理解的，当然也可以用字典，注意字典的键要是不可变类型。