最短路径

使用动态规划进行双向替换路径和 k 最短路径搜索

概述

ShortestPaths 构成论文源代码。它使用动态规划检查双向替换路径和k 最短路径搜索的优化。所提出的算法记住了父路径搜索的状态，并在搜索后续路径时检索它们。在树参数、顺序、密度和图的拓扑结构的参数分析中对优化进行了实验验证。替换路径问题在边缘专有和 节点专有变体以及在线和离线版本上都得到了解决。关于 k 最短路径问题，k执行在线替换路径搜索，遵循Yen的算法和Lawler的修改，同时利用已开发的具有动态规划的双向搜索。 Dijkstra算法用于最短路径搜索，并引入了改进的 Erdős-Rényi随机图模型，控制图的密度和拓扑。更具体地说，小世界属性由图的拓扑结构捕获，从而产生更真实的表示。

k-最短路径搜索支持的四种方法是：

1. 日元 + Dijkstra
2. 劳勒 + 迪杰斯特拉
3. 劳勒 + 投标。迪杰斯特拉
4. 劳勒 + 投标。迪杰斯特拉 + DP

PriorityQueue类被实现为heapq的包装器，使用 <priority, entry_counter, entry> 三元组，如此处所建议的。

论文导师：Prof. Kostas Siozios

安装

$ conda install -c mattasa shortestpaths

$ pip install shortestpaths

用法

$ ksp [OPTIONS] COMMAND [OPTIONS]

Options:
  -n INTEGER                      number of nodes (used when path is None)
                                  [default: 100]
  -k INTEGER                      number of shortest paths to be generated
                                  [default: 1]
  --weighted / --no-weighted      [default: True]
  --directed
  --weights-on [edges|nodes|edges-and-nodes]
                                  [default: edges-and-nodes]
  --max-edge-weight INTEGER       [default: 1000]
  --max-node-weight INTEGER       [default: 50]
  -y, --yen
  -l, --lawler
  -b, --bidirectional             use bidirectional shortest path search
  -p, --parallel                  use multiprocessing
  -d, --dynamic                   use dynamic programming
  -s, --seed INTEGER              fixes the random graph
  --layout-seed INTEGER           fixes the random initialization of the
                                  spring_layout.  [default: 1]
  --show-graph                    plots up to 8 paths
  --save-graph                    format: png
  -v, --verbose                   prints the generated paths

replacement-paths Options:
  -f, --failing [edges|nodes]  Setting what to fail, path edges or path nodes,
                               in order to produce the replacement paths.
                               [default: nodes]

  --online                     When online, the path up until the failure is
                               kept as it is (the algorithm is getting
                               informed upon meeting the failed node or edge),
                               whereas when not online, a new search starts
                               from the source, ignoring the parent-path (the
                               algorithm is a priori informed about the
                               failure).

加载图表

可以使用以下选项加载NetworkX格式的图形：

  --path TEXT                     The NetworkX-file path to read the graph
                                  from. If not provided, a random graph of n
                                  nodes will be generated. Supported formats:
                                  [.adjlist, .edgelist, .gexf, .gml, .gpickle]
                                  Note that .adjlist does not include weights.
  -s, --source TEXT               If a graph is not provided, the source
                                  defaults to node 1.
  -t, --target TEXT               If a graph is not provided, the target
                                  defaults to node n.
  --nodetype TEXT                 convert nodes to this type  [default: int]
  --comments TEXT                 marker for comment lines  [default: #]
  --delimiter TEXT                Separator for node labels. The default is
                                  whitespace.  [default:  ]
  --encoding TEXT                 [default: utf-8]

示例格式：.edgelist

import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([[1, 2, 5], [1, 3, 6], [1, 4, 3], [2, 3, 1], [2, 4, 6]])
nx.write_weighted_edgelist(G, "testgraph.edgelist")

testgraph.edgelist内容：

1 2 5
1 3 6
1 4 3
2 3 1
2 4 6

例子

终端

$ ksp -v
$ ksp --show-graph -k 5 -n 100
$ ksp -v -d -k 20 -n 1000
$ ksp --seed 1 --show-graph -n 200 replacement-paths --failing edges
$ ksp --seed 1 --show-graph -n 200 replacement-paths --failing edges --online

$ ksp -v -d -s <source> -t <target> --path <path-to-graph> --directed -k 50
$ ksp -v -d -s <source> -t <target> --path <path-to-graph> replacement-paths

Python

import shortestpaths as sp

k_paths = sp.k_shortest_paths(G, s, t, k)
print("k_paths:")
sp.print_paths(k_paths)
sp.plot_paths(k_paths, G)

print()

mode = {"failing": "edges", "online": True}
r_paths = sp.replacement_paths(G, s, t, **mode)
print("r_paths:")
sp.print_paths(r_paths)
sp.plot_paths(r_paths, G, mode)

测试

$ pytest --cov=shortestpaths shortestpaths

图模型

目标

1. 控制图密度
2. 控制图拓扑

节点距离

利用节点的增量命名，两个节点之间的距离由节点ID的差异表示。例如，节点 1 和节点 5 的距离为 4。注意这里的距离与对应的边权重无关，不影响算法执行，仅在创建图时使用。

在简单、无向、完全图 (α) 中，距离为x的节点对的频率由以下行给出：

而对于有向图 (β)，这条线是：

小世界财产

该模型构成了Erdős-Rényi 模型的 Gilbert 版本的变体，其中边缘概率不均匀。更具体地说，连接远距离节点的边会受到惩罚，从而避免以极少跳数到达目标的不切实际路径。这样，小世界属性被图的拓扑捕获，这意味着节点倾向于形成小社区。

边权重

边缘权重是从 [0, MAX_EDGE_WEIGHT] 范围内随机选择的，相对于相邻节点的距离有偏差。也就是说，连接远距离节点的边往往会受到惩罚。

概率分布

为了调节边缘距离分布的截止点，使用了 sigmoid 方程，就像低通滤波器一样。为了形成最终的概率分布方程，从 1 中减去 sigmoid 方程，因为距离越小概率越大。Fillaly，结果乘以初始概率p ₀，进一步控制图形密度。

预期节点距离分布

预期图密度

模型摘要

所提出的图模型使用 3 个参数：

• c：乙状结肠中心。调节图形密度，并定义边缘距离分布的截止点。
• λ : sigmoid 梯度。控制截止点周围的区域。
• p ₀：初始概率。调节图形密度。它本质上是吉尔伯特模型在其他两个参数形成的图上的应用。

一个。节点距离概率分布
b。
n = 100 c的完整图上的节点距离分布。应用 a 的概率分布后的真实节点距离分布。在 b 的完整图上。
d。_{p 0} = 0.7的节点距离概率分布。
e. 应用 d 后的预期节点距离分布。到 b。
F。e的实例化。围绕所需拓扑的受控随机性是显而易见的。

用法

import shortestpaths as sp

# adj_list format: [{(neighbor, hop_weight),},]
# G: nx.Graph or nx.DiGraph
adj_list, G = sp.random_graph(n,
                              weighted=True,
                              directed=True,
                              weights_on="edges",
                              max_edge_weight=100,
                              random_seed=None,
                              center_portion=0.2,
                              gradient=0.5,
                              p_0=0.7)

# inverted graph for reverse search
adj_list_reverse = sp.adj_list_reversed(adj_list)

应用动态规划

关于离线替换路径，该算法对基本路径进行 2 次搜索。第一个是简单的路径搜索。第二个是 记忆过程，其中，知道路径，因此知道哪些节点/边会失败，算法只记忆对应于每个路径节点的状态。更具体地说，双向搜索的每个方向都会记住所描述的状态，直到相遇边缘 的搜索。对于对应于基路径的前向搜索访问的失败边/节点的替换路径，前向搜索检索其在失败项目之前的状态，反向搜索检索最后记录的状态，即相遇边之前的状态. 同样，在会议边缘之后失败的项目则相反。

在线对应，前向搜索的状态无法记忆，因为起始节点随着每个替换路径而变化。因此，动态规划仅用于反向子搜索。此外，这一次不需要保存状态。对于 2 次搜索中的第二次，单向搜索从目标节点开始，往回走，每当它要访问一个路径节点时，就开始相应的双向替换路径搜索，使用当前状态作为反向状态.

最后，k-最短路径搜索包括执行k个在线替换路径搜索，遵循Yen 的方法和Lawler 的 修改，其中显然没有执行前面提到的第一次搜索，因为父路径是已知的。

状态检索 | 替换路径离线

状态检索 | 在线替换路径

剖析

CPU 时间 vs n vs 密度

k: 10 c: 0.15 p _max : 0.28

CPU 时间 vs n vs k

c: 0.15 p ₀ : 0.3 p _max : 0.28

结论

• 在测试的场景中，DP使用Yen的方法和Lawler的修改对双向 k 最短路径搜索进行了1-46%的优化。
• 图密度和图拓扑对算法的性能起着重要作用，并且可以有效地补充图顺序以进行更全面的研究。

执照

GNU 通用公共许可证 v3.0

(C) 2020，Athanasios Mattas
atmattas@physics.auth.gr