# 狄克斯特拉算法

### 应用场景

1. 找出最快路径；
2. 物物交换，比如用一块钱换法拉利；

你在前一章使用了广度优先搜索，它找出的是段数最少的路径（如第一个图所示）。如果你 要找出最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉 算法（Dijkstra’s algorithm）。

![数字代表分钟](/files/-LbkFF4hGgY_cC5ccjV1)

使用广度优先搜索，会得到的最佳路线是起点——A——终点，使用狄克斯特拉算法，会得到的最佳路线是起点——B——A——终点。

狄克斯特拉算法包含4个步骤。

 (1) 找出“最便宜”的节点，即可在最短时间内到达的节点。（B比A便宜，所以选B）

 (2) 更新该节点的邻居的开销，其含义将稍后介绍。（更新从B到相邻节点的时间开销，发现从起点——A的时间从6缩短到了5；）

 (3) 重复这个过程，直到对图中的每个节点都这样做了。 （3比5便宜，所以选3，去A）

(4) 计算最终路径。

狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。

带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。要计算非加权图中的最短路径，可使用广度优先搜索。要计算 加权图中的最短路径，可使用狄克斯特拉算法。图还可能有环，而 环类似右面这样。 这意味着你可从一个节点出发，走一圈后又回到这个节点。

![](/files/-LbkHX1GVndEBvqaMqfU)

在无向图中，每条边都是一个环。狄克斯特拉算法只适用于有向无环图（directed acyclic graph，DAG）。因为绕环会增加总权重，绕环的路径不可能是最短路径。

### 负权边

这是因为狄克斯特拉算法这样假设：**对于处理过的海报节点，没有前往该节点的更短路径。** 这种假设仅在没有负权边时才成立。因此，不能将狄克斯特拉算法用于包含负权边的图。在包含 负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼福德算法（Bellman-Ford algorithm）。

### Python代码实现

找出从起点到终点的最快路径

```python
# the graph
graph = {}#创建一个散列表存储节点的所有邻居
graph["start"] = {}#创建另外的一个散列表，存储start节点到其他边的权重
graph["start"]["a"] = 6
graph["start"]["b"] = 2

#要获取起点的所有邻居，可像下面这样做。
#>>> print graph["start"].keys() 
#["a", "b"]

graph["a"] = {}
graph["a"]["fin"] = 1

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

graph["fin"] = {}#终点没有任何邻居

# the costs table
#你不知道到终点需要多长时间。对于还不知道的开销，你将其设 置为无穷大。
#在Python中能够表示无穷大吗？你可以这样做： infinity = float("inf")
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# the parents table
#存储父节点的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []
#用一个数组来记录处理过的节点

#函数find_lowest_cost_node找出开销最低的节点
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    # Go through each node.
    for node in costs:#遍历所有的节点
        cost = costs[node]
        # If it's the lowest cost so far and hasn't been processed yet...
        if cost < lowest_cost and node not in processed:
        #如果当前节点的开销更低且未处理过，
            # ... set it as the new lowest-cost node.
            lowest_cost = cost
            #就将其视为开销最低的节点。
            lowest_cost_node = node
    return lowest_cost_node

# Find the lowest-cost node that you haven't processed yet.
node = find_lowest_cost_node(costs)
#在未处理的节点中找出开销最小的节点；
# If you've processed all the nodes, this while loop is done.
while node is not None:#这个while循环在所有节点都被处理后才结束。
    cost = costs[node]
    # Go through all the neighbors of this node.
    neighbors = graph[node]
    for n in neighbors.keys():#遍历当前节点的所有邻居
        new_cost = cost + neighbors[n]
        # If it's cheaper to get to this neighbor by going through this node...
        #如果当前节点前往该邻居更近，则更新该邻居的开销。
        if costs[n] > new_cost:
            # ... update the cost for this node.
            costs[n] = new_cost
            # This node becomes the new parent for this neighbor.
            parents[n] = node
            #同时将该邻居的父节点设置为当前节点；
    # Mark the node as processed.
    processed.append(node)
    #将当前节点标记为处理过
    # Find the next node to process, and loop.
    node = find_lowest_cost_node(costs)
    #找出接下来要处理的节点，并循环

print ("Cost from the start to each node:")
print (costs)

输出：
Cost from the start to each node:
{'a': 5, 'b': 2, 'fin': 6}

#阿西吧，有些没看懂啊这一大串代码

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://data-structure-and-algorithm.gitbook.io/project/tu/ke-si-te-la-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.