Dijkstra算法--最短路径规划

发表于 更新于 分类于 ， 本文字数： 2.4k 阅读时长 ≈ 2 分钟

摘要

迪杰斯特拉算法(Dijkstra)，用来计算一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

1.算法思想

1.1 计算方法

这个视频讲的比较清楚：【算法】最短路径查找—Dijkstra算法

下面是文字版总结：

将带权图的顶点集合V分为两个子集合，已知最短路径集合S和未确定最短路径集合T。

第一步将起点顶点\(v_0\)加入集合S中，并计算该点到集合T中所有点的权（路径距离）。记录表格（或向量），内容为起点到其余各点的距离（不相连则记为无穷）。

第二步将表格中的最小值对应的顶点加入集合S，并计算该点到集合T中所有点的权，更新集合T对应顶点的距离表格（比较留下最短路径）。

第三步重复第二步直到集合T为空集。所得距离表格即为所求起点到各点的最短路径。

一句话概括：按路径长度递增顺序，将集合T中的各点加入到集合S中。

1.2 证明

  1. 定理1：集合S中的点是按照长度递增顺序加入的。

  2. 定理2：起点\(v_0\)到下一个由T加入S的顶点\(v_k\)必然为弧\((v_0,v_k)\)或者是经过集合S内的点的路径。

证明内容为：通过Digkstra算法得到的是起点到各顶点的最短距离。因为第一步将起点加入了集合S且每次更新会留下最短距离，所以证明内容等价于：在定理2条件下，加入S的顶点\(v_k\)对应的距离是\(v_0\)到\(v_k\)的最短距离。

反证法：假设\(v_0\)到\(v_k\)的最短路径中有一个点或多个点不在集合S中，那么必然存在顶点在T中且路径距离比此路径距离还短的点，与定理1矛盾，假设不成立。

2.实例代码

2.1 题目（改编自PAT甲级1003 Emergency）

你是一个戍守边疆的大将军，管辖许多堡垒，每个堡垒有一定的可以调动的人员，你需要在敌军入侵时尽快从你所在的位置赶过去，并尽可能的多带人马。调动人员需要虎符，所以你必须亲自到场才能调动，但尽快赶到是第一优先级。

input：

第一行输入4个参数：

N -- 管理的堡垒数量N(≤500)(编号0到N-1)

M -- 堡垒由M条路相连

\(c_1\) -- 你当前所在的堡垒位置

\(c_2\) -- 敌军入侵的堡垒位置

第二行输入N个整数，分别对应各个堡垒的可调动人员。

接下来的M行每行有3个整数，分别为堡垒1，堡垒2，和它们之间的路的距离。

output：

最短路径的距离和最多能带的队伍数量

Sample Input:

1
2
3
4
5
6
7
8
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:

1
2 4

代码 

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
65
66
67
68
# N number of cities
# M number of roads
# C1 strart
# C2 end
# team_num number of rescue teams 
# adjacent 连接矩阵

def Dijkstra(adjacent,C1,C2):
    long = 0
    dist = [Max for i in range(N)]
    dist[C1] = 0
    flag_node = [C1]                                            # 标记已经确定最短路径的列表
    last_node = [0 for i in range(N)]                              # 上一节点
    for i in range(N):                                          # 循环直到所有节点都被标记
        if C2 in flag_node:                                     # 如果C2已经被确定，退出循环
            long = dist[C2]
            break
        # 如果C2未被确定，从当前路径开始寻找下一节点
        for i in range(N):
            temp_dist = adjacent[flag_node[-1]][i]
            if (i not in flag_node) and (temp_dist != Max):  #查询该节点未确定的通路
                if dist[i] > (dist[flag_node[-1]] + temp_dist): #判断是否需要更新
                    dist[i] = dist[flag_node[-1]] + temp_dist
                    last_node[i] = flag_node[-1]
        #寻找最小值进行标记
        mini = Max
        for i in range(N):
            if i not in flag_node:
                if dist[i] < mini:
                    mini = dist[i]
                    mini_index = i
        flag_node.append(mini_index)
    return last_node
    
def GetNL(last_node):
    num = 0
    long = 0
    now_node = C2
    while now_node != C1:
        num += team_num[now_node]
        long += 1
        now_node = last_node[now_node]
    return long,num+team_num[C1]

Max = 2147483647
height = 10000
#接收数据
N,M,C1,C2 = map(int,input().split())
team_num = list(map(int,input().split()))
# 建立连接矩阵
adjacent = [ [Max for i in range(N)] for i in range(N) ]
for i in range(N):
    adjacent[i][i] = 0
for i in range(M):
    a,b,l = map(int,input().split())
    l = l*height       #分配权重,利用权重将队伍数量问题也归结到距离问题，但归为次要因素。
    adjacent[a][b] = l - team_num[a]
    adjacent[b][a] = l - team_num[b]


# 使用Dijkstra算法
# num 总共医疗数量
# long 总路程
last_node = Dijkstra(adjacent,C1,C2)
long,num = GetNL(last_node)
if long ==0:
    long = 1
print(long,num)