最短路径

最短路径（Dijkstra方法）

求两点之间的最短路径

最短路径（Dijkstra）和最小生成树（prim， kruskal）的区别：

最短路径：是两个点之间的最短路径

最小生成树：是这几个节点之间的链接距离最短，但是不能够保证两点之间的距离一定是最短的

步骤（有向图）

我们的目标图为（使用邻接矩阵的方法）：

0 1 2 3 4 5
0 ∞ ∞ 10 ∞ 30 100
1 ∞ ∞ 5 ∞ ∞ ∞
2 ∞ ∞ ∞ 50 ∞ ∞
3 ∞ ∞ ∞ ∞ ∞ 10
4 ∞ ∞ ∞ 20 ∞ 60
5 ∞ ∞ ∞ ∞ ∞ ∞

  1. 我们先创建一个数组

    这个数组的每一个元素都是一个节点，每一个元素都要包括：

    • 这个节点是否被选取过了（如果被选取过了就是证明这个节点的最短路径已经找到了）

    • 起始位置到这个节点的距离

    • 这个节点的上一个节点是谁

    节点名称 节点状态 节点权重 前一个节点
    0 0 ∞ null
    1 0 ∞ null
    2 0 ∞ null
    3 0 ∞ null
    4 0 ∞ null
    5 0 ∞ null

  2. 开始填充这个数组：

    如果我们假设要找出 节点0到各个节点的最短距离的话，我们就需要从节点1开始遍历整个图的邻接矩阵

    • 我们先个节点1的节点状态标上1证明这个节点到1的最短路径已经找到
    • 然后遍历图的领接矩阵的这一行看他到各个节点的距离和节点权重比较，如果邻接矩阵中的值小于，判断数组中的节点权重，那么就更新节点权重，并把前一个节点的状态设置为 1

    第一步：

    节点名称 节点状态 节点权重 前一个节点
    0 1 ∞ null
    1 0 ∞ null
    2 0 10 0
    3 0 ∞ null
    4 0 30 0
    5 0 100 0

等排完数组之后，我们找出节点权重里面最小的，收入最优路径中，这里面最小的节点权重为：2， 并把它的节点状态设置成1

第二步：

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 0 ∞ null
2 1 10 0
3 0 10 + 50 2
4 0 30 0
5 0 100 0

找出未标记节点的节点权重最小的：4，并把它的节点状态设置成1

第三步：

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 0 ∞ null
2 1 10 0
3 0 30 + 20 4
4 1 30 0
5 0 30 + 60 4

找出未标记节点的节点权重最小的：3， 并把它的节点状态设置为1

第四步：

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 0 ∞ null
2 1 10 0
3 1 30 + 20 4
4 1 30 0
5 0 30 + 20 + 10 3

找出未标记节点权重最小的是：5，并把它的节点状态设置为1

最后结果为：

循环跳出条件为找出未标记节点的最小节点权重为∞ 则跳出循环，或者节点都被标记了

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 0 ∞ null
2 1 10 0
3 1 30 + 20 4
4 1 30 0
5 1 30 + 20 + 10 3

步骤（无向图）

0 1 2 3 4 5
0 ∞ ∞ 10 ∞ 30 100
1 ∞ ∞ 5 ∞ ∞ ∞
2 10 5 ∞ 50 ∞ ∞
3 ∞ ∞ 50 ∞ 20 10
4 30 ∞ ∞ 20 ∞ 60
5 100 ∞ ∞ 10 60 ∞

同样还是县创建一个数组：

节点名称 节点状态 节点权重 前一个节点
0 0 ∞ null
1 0 ∞ null
2 0 ∞ null
3 0 ∞ null
4 0 ∞ null
5 0 ∞ null

同样还是从节点0开始：

  1. 第一步：

    节点名称 节点状态 节点权重 前一个节点
    0 1 ∞ null
    1 0 ∞ null
    2 0 10 0
    3 0 ∞ null
    4 0 30 0
    5 0 100 0

等排完数组之后，我们找出节点权重里面最小的，收入最优路径中，这里面最小的节点权重为：2， 并把它的节点状态设置成1

  1. 第二步：
节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 0 10 + 5 2
2 1 10 0
3 0 10 + 50 2
4 0 30 0
5 0 100 0

找出未标记的节点权重最小的：1，并把它的节点状态设置成为1

  1. 第三步：
节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 1 10 + 5 2
2 1 10 1
3 0 10 + 50 2
4 0 30 0
5 0 100 0

找出标记节点权重最小的：这里为 4 ，并把它的状态设置成为1

  1. 第四步：
节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 1 5 2
2 1 10 1
3 0 20 + 30 4
4 1 30 0
5 0 100 0

找出标记节点权重最小的：这里为 3 ，并把它的状态设置成为1

  1. 第五步：
节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 1 5 2
2 1 10 1
3 1 20 + 30 4
4 1 30 0
5 0 20 + 30 +10 3

找出标未记节点权重最小的：这里为5，并把它的状态设置成1

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 1 5 2
2 1 10 1
3 1 20 + 30 4
4 1 30 0
5 1 20 + 30 +10 3

跳出循环条件：节点状态全部为1，或者最小节点的节点权重为 无穷

回溯步骤

以无向图为例：我们追溯一下节点 0-5的最短路径：

节点名称 节点状态 节点权重 前一个节点
0 1 ∞ null
1 1 5 2
2 1 10 1
3 1 20 + 30 4
4 1 30 0
5 1 20 + 30 +10 3

我们先找到节点5的前一个节点位置：这里为3

我们在找到节点3的前一个节点的位置：这里为4:

再找出节点4的前一个节点的位置：这里为0

0 == 0跳出循环：

最后回溯结果为 0 4 3 5

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 最短路径

def get_shortest_path(map, Record_array, start):

    s = start
    # 因为是从s开始的，所以先把s位置的权重设置为零 应为 s - s的权重为零
    Record_array[s][1] = 0
    Record_array[s][0] = 1

    while True:
        
        # 遍历一下s作为起点， 和s相连的节点的权重
        for column_index, data in enumerate(map[s]):
            # 遍历与这个几点相连的所有节点的权重
            if Record_array[column_index][0] != 1:
                if Record_array[column_index][1] > Record_array[s][1] + data:
                    Record_array[column_index][1] = Record_array[s][1] + data
                    Record_array[column_index][2] = s
        min_num = 100000
        min_index = -1
        for i in range(len(Record_array)):
            if Record_array[i][0] != 1:
                if Record_array[i][1] < min_num:
                    min_num = Record_array[i][1]
                    min_index = i

        s = min_index
        # 先给s位置设置为1
        Record_array[s][0] = 1

        record_num = 0
        for i in range(len(Record_array)):
            if Record_array[i][0] == 1:
                record_num += 1
        if record_num == len(Record_array) or Record_array[s][2] == 100000:
            break

def track(Record_array, start, end):
    track_list = [end]
    while end != start:
        end = Record_array[end][2]
        track_list.append(end)
    return track_list


# 图的邻接矩阵
map = [
    [100000, 100000, 10, 100000, 30, 100],
    [100000, 100000, 5, 100000, 100000, 100000],
    [10, 5, 100000, 50, 100000, 100000],
    [100000, 100000, 50, 100000, 20, 10],
    [30, 100000, 100000, 20, 100000, 60],
    [100, 100000, 100000, 10, 60, 100000],
]

#  创建一个记录数组
Record_array = [ [0, 100000, -1] for i in range(len(map))] 

get_shortest_path(map, Record_array, 0)

track_list = track(Record_array, 0, 5)

print(track_list)