贪婪(Greedy)演算法

贪婪演算法是考虑局部最佳解，在子结构中解决问题是相当有利的，但放入整体问题中，不一定会是最佳解。

贪婪演算法与动态规划的不同在於它对每个子问题的解决方案都做出选择，不能回退。动态规划则会储存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
参考资料：wiki

戴克斯特拉演算法(Dijkstra's algorithm)

Dijkstra's algorithm与Bellman-Ford Algorithm一样，能够正确求出有向图的最短路径。但图形中若有负值时，Dijkstra's Algorithm无法求出正确路径。回圈中有负环时，并不存在最短路径。Bellman-Ford Algorithm可以判断出最短路径不存在，但Dijkstra's Algorithm会将错误的判断当作正确答案。因此，无法使用Dijkstra's Algorithm无法用於负环的图形。
总结：若边没有负环，选择执行时间的Dijkstra's Algorithm较佳。边有负环时，则使用Bellman-Ford Algorithm，执行时间虽长，但可以正确求解。

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

from heapq import *
City = {}
G = {}
pq = []
# dis为101个元素的串列，每个元素值都是1000000
dis = [1000000]*101
# v为101个元素的串列，每个元素值都是0
v = [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

n = 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)
    e2 = Edge(b, a, w)
    if a in G.keys():
        G[a].append(e1)
    else:
        G[a]=[e1]
    if b in G.keys():
        G[b].append(e2)
    else:
        G[b]=[e2]

# 输入起点节点名称，传入getCityIndex转换成节点编号，变数s参考到此节点编号
s = getCityIndex(input())
# 建立有两个元素的tuple，目标点起始点为s
p = (0, s) #(距离,目标点)
heappush(pq, p)
# 表示出发点的最短距离为0
dis[s]=0

while len(pq) > 0:
    # 使用heappop取出最上面元素（起始点到此点是最短距离）
    p = heappop(pq)
    # s为p的第二个元素，为该边的目标点起点，是下一个起点
    s = p[1]
    # 若v[s]=0，设定v[s] = 1，表示起始点到节点编号s是最短路径
    if v[s] == 0:
        v[s] = 1
        for edge in G[s]:
            if v[edge.t] == 0:
                if dis[edge.t] > dis[s] + edge.w:
                    dis[edge.t] = dis[s] + edge.w
                    p = (dis[edge.t], edge.t) #(距离,目标点)
                    heappush(pq, p)

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

程序码参考资料：资料结构使用Python

负环

负环就是最短路径所形成的循环，若不断经过此循环就可以获得更小的值，会造成无法在有限步骤中获得最佳路径。