python - 在有向加权图中具有恰好 k 个边的最短路径生成(编辑:每个节点只访问一次)
问题描述
以下代码来自https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/。所有功劳归于 Pranchalk。
我正在处理生成 k 边最短路径的问题。下面的代码给出了具有预定义 k 的最短“距离”。
但是,我需要“路径” 对于路径下面的代码,路径似乎是:
0 --> 2 --> 3 。
编辑:Ajay 的代码解决了这个问题。但是,每个节点只需要访问一次。我在原始问题中没有提到这一点。我已经包含了一个额外的数据集来测试它。
# Python3 program to find shortest path
# with exactly k edges
# Define number of vertices in the graph
# and inifinite value
# A naive recursive function to count
# walks from u to v with k edges
def shortestPath(graph, u, v, k):
V = 4
INF = 999999999999
# Base cases
if k == 0 and u == v:
return 0
if k == 1 and graph[u][v] != INF:
return graph[u][v]
if k <= 0:
return INF
# Initialize result
res = INF
# Go to all adjacents of u and recur
for i in range(V):
if graph[u][i] != INF and u != i and v != i:
rec_res = shortestPath(graph, i, v, k - 1)
if rec_res != INF:
res = min(res, graph[u][i] + rec_res)
return res
# Driver Code
if __name__ == '__main__':
INF = 999999999999
# Let us create the graph shown
# in above diagram
graph = [[0, 10, 3, 2],
[INF, 0, INF, 7],
[INF, INF, 0, 6],
[INF, INF, INF, 0]]
u = 0
v = 3
k = 2
print("Weight of the shortest path is",
shortestPath(graph, u, v, k))
# This code is contributed by PranchalK
预期结果是:
[0,2,3]
0是起始节点,3是结束节点。边数为 2。路径为 0 --> 2 --> 3
编辑:Ajay 的回答非常接近。但是,每个节点只需要访问一次。很抱歉,我最初没有提到这一点。这是一个更大的数据来测试。
graph = [[0, 10, 3, 2,4,1],
[1, 0, 3, 7,4,1],
[2, 8, 0, 6,0,1],
[4, 1, 3, 0,1,2],
[3, 1, 2, 2,4,1],
[7, 1, 3, 0,3,3]]
Weight of the shortest path is 14
Shortest path is [0, 2, 0, 2, 3]
解决方案
通过检查Shortest Paths中现有的 NetworkX 算法,似乎这些算法都不允许直接获得两个节点之间的所有简单路径以及相应的权重。
所以有必要分别做这两件事:
- 计算两个给定节点之间的所有路径,并只保留那些长度
k
- 然后计算每条路径的权重并选择权重较小的路径
通用解决方案
def shortest_path_k_edges(graph, source, target, k):
'''
Computes the shortest simple path with
exactly k edges of a weighted graph
between the specified source and target
----
graph: np.array
Adjacency matrix for the graph
source: int
Source node
target: int
Target node
k: int
Amount of edges of the path
----
Returns:
Shortest k length path
'''
import networkx as nx
# Builds graph from the adjacency matrix
g = nx.from_numpy_array(graph)
# Generates all simple paths (no repeated nodes)
# in the graph from source to target
all_paths = nx.all_simple_paths(g, source, target)
# Keeps only paths with k edges
paths = [i for i in all_paths if len(i) == k+1]
# Compute the weights of each of the paths
# using the adjacency matrix
weights = [sum(graph[i[j], i[j+1]]
for j in range(len(i)-1))
for i in paths]
# Return path of minimum weight, and
# corresponding weight
min_w = min(weights)
return paths[weights.index(min_w)], min_w
输出
让我们使用建议的参数检查结果:
u = 0
v = 3
k = 2
INF = 999999999999
import numpy as np
graph = np.array(
[[0, 10, 3, 2],
[INF, 0, INF, 7],
[INF, INF, 0, 6],
[INF, INF, INF, 0]])
path, weight = shortest_path_k_edges(graph, u, v, k)
print(path)
# [0, 2, 3]
print(weight)
# 9