最短路徑演算法

最短路徑是在賦予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種資料結構，人工智慧、數據分析、邏輯思考的原理和應用全圖解