打造現今最重要的演算法“最短”路徑規劃

白話說就是找到從一個節點到另一個節點的最短路徑～～路由算法及地圖應用UBER導航等等滴～～～

兩個常見的最短路徑演算法：

• Dijkstra's Algorithm（迪克斯特拉算法）：
  用於找到帶有非負權重的加權圖中節點之間的最短路徑。
  它使用了一個稱為「貪心策略」的方法來選擇下一個要擴展的節點。
  這個演算法的時間複雜度是O((V+E)logV)，其中V是節點數，E是邊數。

import heapq

# 從起始節點到所有其他節點的最短路徑
def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 使用示例
graph = {'A': {'B': 1, 'C': 4},
         'B': {'A': 1, 'C': 2, 'D': 5},
         'C': {'A': 4, 'B': 2, 'D': 1},
         'D': {'B': 5, 'C': 1}}

result = dijkstra(graph, 'A')
print(result)

• Bellman-Ford Algorithm（貝爾曼-福特算法）：
  用於找到任意加權圖中節點之間的最短路徑，可以處理存在負權重的情況。
  這個演算法通過不斷更新每個節點的最短距離來進行工作，直到達到最優解。
  這個演算法的時間複雜度是O(VE)，其中V是節點數，E是邊數。

# 起始節點到所有其他節點的最短路徑，同時也能檢測是否存在負權環
def bellman_ford(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                print("圖形中存在負權環")
                return

    return distances

# 使用示例
graph = {'A': {'B': 1, 'C': 4},
         'B': {'A': 1, 'C': 2, 'D': 5},
         'C': {'A': 4, 'B': 2, 'D': 1},
         'D': {'B': 5, 'C': 1}}

result = bellman_ford(graph, 'A')
print(result)

什麼是負權環（Negative Cycle）？？？

負權環（Negative Cycle）是指在有向圖中，從某個起始節點出發，經過若干條邊回到起始節點的路徑，使得路徑上所有邊的權重總和為負數。在最短路徑問題中，如果存在負權環，則最短路徑可能無法確定。這是因為如果可以無限次地繞負權環，那麼就可以無限次地減小總路徑權重～～