个人数学建模算法库之图的最短路径模型

图论术语

路的长度：赋权图的路经过的边的权和

最短路：从顶点$v_i$到顶点$v_j$的路中，长度最小的一条路。

顶点间的距离：顶点$v_i$到顶点$v_j$的最短路的长度。记作$d(u_0,v_0)$

固定起点的最短路

模型简介

已知赋权无向图$G(V,E,W)$

固定顶点$u_o$ ,求$u_0$到其余顶点$v$的最短路及距离$d(u_0,v)$

Dijkstra(迪克斯特拉)算法

算法思想:最短路径的子路也是最短路。固定$u_0$,从近到远求出$u_0$到其余顶点之一$v$的最短路和距离，直至遍历完所有顶点(或到某一特定顶点$v_0$ ）。

记号说明：

算法步骤

• 令$d_{now}(u_0)=0$.对于其他顶点$v\ne u_0$ ，令$d_{now}(v)=\infty$ ,$parents(v)=u_0$ .令 S 0 = { u 0 } S_0=\{u_0\} S0​={u0​},$i=0$
• 对于所有的$v\notin S_i$ ,令 ( v ) = min ⁡ u ∈ S i { d n o w ( v ) , d n o w ( u ) + w ( u v ) } \displaystyle (v)=\min_{u\in S_i}\{d_{now}(v),d_{now}(u)+w(uv)\} (v)=u∈Si​min​{dnow​(v),dnow​(u)+w(uv)}.若通过$u$更新了$d_{now}(v)$,则令$parents(v)=u$;否则不变。
• 寻找$\underset{v\notin S_i}{\min }{d}_{now}(v)$ ,记该顶点为$u_{i+1}$,令 S i + 1 = S i ∪ { u i + 1 } S_{i+1}=S_i\cup\{u_{i+1}\} Si+1​=Si​∪{ui+1​}
• 若$i=|V|-1$或者$v_0$进入$S_i$,算法终止；否则重复2,3步

算法结束后，$S_i$为最短路径集。$d_{now}(v)$为距离集。

算法局限:要求权值为正数

Matlab代码

% Dijkstra.m

function [path, distance] = Dijkstra(G, u0, v0)
    % Dijkstra算法求最短路径

    % 初始化参数
    n = G.numnodes;
    nodes = 1:n;
    i = 0;
    d_now = ones(n, 1) * inf;
    d_now(u0) = 0;
    parents = ones(n, 1) * u0;
    in_s = u0;

    history = [];
    % 遍历所有终点或v0进入最短路径集
    while (i ~= n - 1) && ~(ismember(v0, in_s))
        not_in_s = setdiff(nodes, in_s);

        for v = not_in_s

            for u = in_s
                % 查找uv间的边
                uv_index = G.findedge(u, v);

                if uv_index
                    % 边存在则获取权
                    w = min(G.Edges.Weight(uv_index));
                    % 计算新的最短距离
                    d_now(v) = min([d_now(v), d_now(u) + w]);

                    if d_now(u) + w <= d_now(v)
                        % 距离发生改变
                        parents(v) = u;
                        % 记录变化
                        history = [history; [u, v]];
                    end

                end

            end

        end

        % 寻找最短距离的顶点
        tmp = d_now;
        tmp(in_s) = inf;
        [~, new_u] = min(tmp);
        new_u = new_u(1);
        % 添加最短路径顶点
        in_s = union(new_u, in_s);
        i = i + 1;
    end

    % 倒溯最短路径
    last = v0;
    path = v0;

    while last ~= u0
        k = find(history(:, 2) == last);
        last = history(k(end), 1);
        path = [last, path];
    end

    distance = d_now(v0);
end

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

示例：

clc,clear

% 输入图的顶点对
E=[ 1 2 2;1 3 8;1 4 1;
    2 3 6;2 5 1;3 4 7;
    3 5 5;3 6 1;3 7 2;
    4 7 9;5 6 3;5 8 2;
    5 9 9;6 7 4;6 9 6;
    7 9 3;7 10 1;8 9 7;
    8 11 9;9 10 1;9 11 2;
    10 11 4];

% 创建并绘制图
G=graph(E(:,1),E(:,2),E(:,3));
figure=plot(G,"EdgeLabel",G.Edges.Weight,'EdgeLabelColor','green');

% 使用Dijkstra算法求得最短路径并在图中标出
[path,distance]=Dijkstra(G,1,11);
highlight(figure,path,'EdgeColor','red','LineWidth',2,"EdgeLabelColor","red");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Python代码

def Dijkstra(G, u0, v0):
    """利用Dijkstra计算最短路径和距离"""

    # 初始化参数
    n = G.number_of_nodes()
    nodes = list(range(1, n + 1))
    d_now = np.ones(n) * np.inf
    d_now[u0 - 1] = 0
    parents = [u0 for i in range(n)]
    s = set()
    s.add(u0)
    history = []
    i = 0

    # 遍历所有终点或v0进入最短路径顶点集
    while (i != n - 1) or (v0 not in s):
        not_s = set(nodes) - s
        for v in not_s:
            for u in s:
                try:
                    # 检查顶点u,v间是否有边
                    w = G.edges[u, v]['weight']
                except:
                    pass
                else:
                    d_now[v - 1] = min([d_now[v - 1], d_now[u - 1] + w])
                    if d_now[u - 1] + w <= d_now[v - 1]:
                        # 顶点最短值改变,记录改变
                        parents[v - 1] = u
                        history.append([u, v])

        # 寻找当前的最小距离点,并加入s集合
        tmp = d_now.copy()
        in_s_index = [i - 1 for i in s]
        tmp[in_s_index] = np.inf
        new_u = np.argmin(tmp) + 1
        s.add(new_u)
        i = i + 1

    # 拼接最终的最短路径
    last = v0
    path = [v0]
    history = np.array(history)
    while last != u0:
        k = np.where(history[:, 1] == last)
        last = history[k[-1][-1], 0]
        path.append(last)

    path = path[-1::-1]
    distance = d_now[v0 - 1]
    return path, distance
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

示例:

# 导库
import networkx as nx
import numpy as np

# 输入边和权
edges = [(1, 2, 2), (1, 3, 8), (1, 4, 1), (2, 3, 6), (2, 5, 1), (3, 4, 7),
         (3, 5, 5), (3, 6, 1), (3, 7, 2), (4, 7, 9), (5, 6, 3), (5, 8, 2),
         (5, 9, 9), (6, 7, 4), (6, 9, 6), (7, 9, 3), (7, 10, 1), (8, 9, 7),
         (8, 11, 9), (9, 10, 1), (9, 11, 2), (10, 11, 4)]

# 创建空图并添加顶点和边权
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 计算顶点位置
pos = nx.spring_layout(G)

# 绘制无权图
nx.draw(G, pos, with_labels=True, font_size=14)

# 绘制最短路径
path,distance=Dijkstra(G,1,11)
shortest_edges=[]
for i in range(np.size(path)-1):
    shortest_edges.append((path[i],path[i+1]))
nx.draw_networkx_edges(G,pos,edgelist=shortest_edges,edge_color='red')

# 追加绘制权
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos,edge_labels=labels,font_color="green")
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

所有顶点间的最短路

模型简介

已知赋权无向图$G(V,E,W)$

求所有顶点对$(u_0,v_0)$之间的最短距离及对应最短路径

Floyd(弗洛伊德)算法

算法思想:依次将每个顶点作为可能的中间点，插入所有的顶点对之间进行判断，若最短距离更新，则将该点记录下来。直到n次之后，得到所有顶点对的最短距离，并通过之间的记录反推最短路径。

记号说明：

算法步骤

• 初始化:令$distances$为图$G$的带权邻接矩阵.设置不相邻的顶点对对应的$distances$元素为$\infty$.令$R=0_{n\times n}$ .$R$对应位置的元素为0，代表两顶点最短路径间无中间点。
• 求距离矩阵和路由矩阵:从顶点$v_1$开始直到$v_n$,取该顶点$v_k$,依次插入到顶点对$(v_i,v_j)$间，若$distances(i,k)+distances(k,j)<distances(i,j)$,说明$v_k$为$(v_i,v_j)$最短路径的中间点。更新$distances(i,j)$为$distances(i,k)+distances(k,j)$.并令$R(i,j)=k$,记录下该中间点。
• 复原路径:要获得$v_i$与$v_j$的最短路径，只需找到其中间点$v_{R(i,j)}$ .再寻找$v_i$与$v_{R(i,j)}$的中间点，$v_j$与$v_{R(i,j)}$的中间点…重复该过程。

算法局限:所有圈的权值和非负

Matlab代码

% Floyd.m

function [distances, paths] = Floyd(G)
    % Floyd算法求所有顶点对之间的最短路径

    % 矩阵初始化
    distances = G.adjacency('weighted');
    n = length(distances);
    distances(distances == 0) = inf;
    distances(1:n + 1:end) = 0;
    R = zeros(n);

    for k = 1:n

        for i = 1:n

            for j = 1:n

                % 插点更新
                if distances(i, k) + distances(k, j) < distances(i, j)
                    distances(i, j) = distances(i, k) + distances(k, j);
                    R(i, j) = k;
                end

            end

        end

    end

    distances = full(distances);

    % 复原路径
    paths = returnPaths(R);

    for i = 1:n

        for j = 1:n

            if i ~= j
                % 添加起点和终点
                paths{i, j} = [i paths{i, j} j];
            else
                paths{i, j} = i;
            end

        end

    end

end
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

% returnPaths.m

function paths = returnPaths(R)
    % 根据路由矩阵返回最短路径矩阵
    n = length(R);
    paths = cell(n);

    for i = 1:n

        for j = 1:n
            paths{i, j} = parse(i, j);
        end

    end
    
    % 递归推导最短路径
    function path = parse(i, j)
        p = R(i, j);

        if p == 0
            path = [];
        else
            left = parse(i, p);
            right = parse(p, j);
            path = [left, p, right];
        end

    end

end
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

示例:

clear,clc

E=[ 1 2 2;1 3 8;1 4 1;
    2 3 6;2 5 1;3 4 7;
    3 5 5;3 6 1;3 7 2;
    4 7 9;5 6 3;5 8 2;
    5 9 9;6 7 4;6 9 6;
    7 9 3;7 10 1;8 9 7;
    8 11 9;9 10 1;9 11 2;
    10 11 4];

G=graph(E(:,1),E(:,2),E(:,3));

n=G.numnodes;

[distances,paths]=Floyd(G)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Python代码

def returnPaths(R):
    """根据路由矩阵还原路径"""
    def parse(i, j):
        """递归解析i,j顶点最短路径"""
        p = R[i, j]
        if p == 0:
            path = []
        else:
            path = [p]
            left = parse(i, p - 1)
            right = parse(p - 1, j)
            path.extend(right)
            for num in left[-1::-1]:
                path.insert(0, num)
        return path

    n, n = np.shape(R)
    paths = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            paths[i].append(parse(i, j))
    return paths


def Floyd(G):
    """Floyd算法求所有顶点间的最短路径"""

    # 初始化矩阵
    distances = nx.to_numpy_matrix(G)
    n, n = np.shape(distances)
    distances[distances == 0] = np.inf
    row, col = np.diag_indices_from(distances)
    distances[row, col] = 0
    R = np.zeros((n, n), dtype=int)

    # 插点更新
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distances[i, k] + distances[k, j] < distances[i, j]:
                    distances[i, j] = distances[i, k] + distances[k, j]
                    R[i, j] = k + 1

    # 复原路径
    paths = returnPaths(R)

    # 路径添加起点和终点
    for i in range(n):
        for j in range(n):
            if i != j:
                paths[i][j].append(j + 1)
                paths[i][j].insert(0, i + 1)
            else:
                paths[i][j] = [i + 1]
    return distances, paths
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

示例:

# 导库
import networkx as nx
import numpy as np
import pandas as pd

# 输入边和权
edges = [(1, 2, 2), (1, 3, 8), (1, 4, 1), (2, 3, 6), (2, 5, 1), (3, 4, 7),
         (3, 5, 5), (3, 6, 1), (3, 7, 2), (4, 7, 9), (5, 6, 3), (5, 8, 2),
         (5, 9, 9), (6, 7, 4), (6, 9, 6), (7, 9, 3), (7, 10, 1), (8, 9, 7),
         (8, 11, 9), (9, 10, 1), (9, 11, 2), (10, 11, 4)]

# 创建空图并添加顶点和边权
G = nx.Graph()
G.add_weighted_edges_from(edges)

# Floyd算法
distances, paths = Floyd(G)

n = G.number_of_nodes()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

d_df = pd.DataFrame(distances, index=range(1, n + 1), columns=range(1, n + 1))
d_df
1
2

p_df = pd.DataFrame(paths, index=range(1, n + 1), columns=range(1, n + 1))
p_df
1
2

库函数

Matab版

[path,distance] = shortestpath(G,u0,v0) # 求u0到v0的最短路径和最短距离

D=distances(G) # 求顶点对间的最短距离矩阵
1
2
3

Python版

import networkx as nx
import pandas as pd

path = nx.dijkstra_path(G, u0, v0)  # Dijkstra算法求两点的最短路径列表
distance = nx.dijkstra_path_length(G, u0, v0)  # Dijkstra算法求两点的最短距离

path = nx.shortest_path(G, u0, v0,weight='weight')  # 求两点的最短路径列表
distance = nx.shortest_path_length(G, u0, v0,weight='weight') # 求两点的最短距离

distances = dict(nx.all_pairs_dijkstra_path_length(G))  # 求顶点对之间的最短距离字典
d_df = pd.DataFrame(distances).T
d_df

paths = dict(nx.all_pairs_dijkstra_path(G)) # 求顶点对之间的最短路径字典
p_df = pd.DataFrame(paths).T
p_df
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16