最短路径演算法

最短路径是在赋予edges权重的「加权图形」里，指定「起点」和「终点」，求出起点到终点之间，权重总和最小的路径。
求取最短路径时，通常edges的权重会用来表示「时间」、「距离」等，一般来说，都不会以负数呈现，但Bellman-Ford algorithm即使权重为负也能正常运作。
下列为几种求取最短路径演算法：

• 贝尔曼-福特演算法(Bellman-Ford algorithm)
• 戴克斯特拉演算法(Dijkstra's algorithm)
• A演算法(A algorithm)

贝尔曼-福特演算法(Bellman-Ford Algorithm)

简单来说，就是用於计算最短路径。Bellman-Ford Algorithm是一种动态规划的演算法，最短路径决定了还能更改，可以用於edges权重为负值的情况。仅能找出单点对所有点的最短路径，不能用於负环的图形上找最短路径，但能侦测图形中使否有负环存在。

影片参考:
https://www.youtube.com/watch?v=obWXjtg0L64

City = {}
G = {}
# qu为串列
qu = []
# dis为101个元素的串列，每个元素值都是1000000
dis = [1000000]*101
# inqu为101个元素的串列，每个元素值都是0
inqu = [0]*101

# 将节点名称转成数字，使用字串p为输入参数，将节点名称p转换成节点编号
def getCityIndex(p):
    # 若p不是City的key，则设定City[p]
    if p not in City.keys():
        # 对应的值为City的长度
        City[p]=len(City)
    #回传City key的对应值
    return City[p]


class Edge:
    def __init__(self, s, t, w):
        # s：边的起点，t：边的终点，w：边的权重
        self.s = s
        self.t = t
        self.w = w

# 使用input输入一个整数到m，int将字串转换数字，表示有几个边要输入
m = int(input())
for i in range(m):
    # 每次输入三个资料，表示边的两个顶点到变数a与b，边的权重到变数w
    a, b, w = input().split()
    a = getCityIndex(a)
    b = getCityIndex(b)
    w = int(w)
    e1 = Edge(a, b, w)
    if a in G.keys():
        G[a].append(e1)
    else:
        G[a]=[e1]

# 输入起点节点名称，传入getCityIndex转换成节点编号，变数s参考到此节点编号
s = getCityIndex(input())
qu.append(s)
# 表示出发点的最短距离为0
dis[s] = 0
# 表示s所表示的节点，已经在伫列qu内
inqu[s] = 1
while len(qu) > 0:
    # 从qu取出最前面的元素储存到p，删除qu最前面元素
    p = qu.pop(0)
    # 表示节点编号p已经从qu中取出
    inqu[p] = 0
    if G.get(p) != None:
        for edge in G[p]:
            # 表示找到出发点s到节点编号edge.tk的更短路径
            if dis[edge.t] > dis[edge.s] + edge.w:
                dis[edge.t] = dis[edge.s] + edge.w
                # 表示edge.t还没加入qu，则将edge.t加入qu
                if inqu[edge.t] == 0:
                    qu.append(edge.t)
                    inqu[edge.t] = 1

for i in range(len(City)):
    print(dis[i]," ",sep="",end="")

程序码参考资料:资料结构使用python

动态规划(Dynamic Programming)

动态规划是分治法的延伸，也就是将大问题分解为小问题，再依次解决。目的是解决递回出现的重复性问题，以空间换取时间。

时间复杂度

假设输入图形的顶点数为n，边数为m，Bellman-Ford algorithm进行n次更新操作的循环就会停止。再加上循环更新操作中，会检视所有的边1次，所以循环的执行时间是O(m)，整体执行时间为O(nm)。

资料来源：演算法图监：26种演算法 + 7种资料结构，人工智慧、数据分析、逻辑思考的原理和应用全图解