狄克斯特拉算法

概述

狄克斯特拉算法——用于在加权图中找到最短路径

ps：

• 广度优先搜索——用于解决非加权图的最短路径问题
• 存在负权边时——贝尔曼-福德算法

下面是来自维基百科的权威解释。

戴克斯特拉算法（英语：Dijkstra’s algorithm，又译迪杰斯特拉算法）由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体；戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s到 t 的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。

最初的戴克斯特拉算法不采用最小优先级队列，时间复杂度是{\displaystyle O(|V|^{2})}(其中{\displaystyle |V|}为图的顶点个数)。通过斐波那契堆实现的戴克斯特拉算法时间复杂度是{\displaystyle O(|E|+|V|\log |V|)} (其中{\displaystyle |E|}是边数) （Fredman & Tarjan 1984）。对于不含负权的有向图，这是当前已知的最快的单源最短路径算法。

Python实现：

# 创建图
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}

print(graph)  # {'start': {'a': 6, 'b': 2}, 'a': {'fin': 1}, 'b': {'a': 3, 'fin': 5}, 'fin': {}}

# 创建开销表

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
print(infinity, type(infinity))

# 创建父节点
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 用来记录处理过的节点
processed = []


def find_lower_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


node = find_lower_cost_node(costs)

while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lower_cost_node(costs)

print(costs)