以下代码来自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]
存储产生min的节点。每个边长<k的权重之和。
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
k_minus_one_path = []
least_sum_node = None
for i in range(V):
if graph[u][i] != INF and u != i and v != i:
rec_res, path = shortestPath(graph, i, v, k - 1)
if rec_res != INF:
if res > graph[u][i] + rec_res:
k_minus_one_path = path
least_sum_node = i
res = graph[u][i] + rec_res
if least_sum_node is not None:
k_minus_one_path.insert(0, least_sum_node)
k_path = k_minus_one_path
return res,k_path
# 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
weight, path = shortestPath(graph, u, v, k)
if weight != INF:
path.insert(0, u) # source
path.append(v) # Destination
print("Weight of the shortest path is", weight)
print("Shortest path is ", path)
通过检查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