给定边的最短路径
Shortest path with given edges
我想使用 k
条边从 source(u) 找到最短路径。这个 solution 似乎有效,但它搜索具有 k
条边的路径到给定节点 v
。如果 k
边在到达 v
之前被覆盖怎么办?我只想要 u
覆盖 k
边的所有路径的最短路径。不需要达到 v
。
上面的代码 link:
# 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, 4, 2, 6, 5],
[INF, 0, 4, 2, 5],
[INF, INF, 0, 4, 3],
[INF, INF, INF, 0, 3],
[INF, INF, INF, INF, 0]]
u = 0
v = 4
k = 3
print("Weight of the shortest path is",
shortestPath(graph, u, v, k))
您或许可以修复该代码(完全不传入或查看 v
- 见下文)。但我建议简单地修改 Dijkstra 的算法,最多从起始节点探索 3 条边。 Dijkstra 从头开始找到所有 shortest-length 条路径。当路径到达其第三个边缘时只需停止它(这将要求您除了保持距离外还保持 edge-counts)。
修改上面的代码也可以,但肯定会更慢,因为除非图形是树,否则您将多次查看每条边。
INF = 999999999999
def nearest_in_k_steps(graph, u, k):
print(f"Entering {u}, {k} steps remaining")
V = len(graph)
# Base case
if k == 0:
return 0, u
# Initialize result
best_dist = INF
best_target = None
# Go to all adjacents of u and recurse
for i in range(V):
if graph[u][i] != INF and u != i:
candidate_dist, candidate_target = nearest_in_k_steps(graph, i, k - 1)
candidate_dist += graph[u][i]
if candidate_dist < best_dist:
print(f"Hmm, path via {i} (d={candidate_dist}) is better than via {best_target} (d={best_dist})")
best_dist = candidate_dist
best_target = candidate_target
print(f"Returning from {u}, {k} steps remaining: d={best_dist} to {best_target}")
return best_dist, best_target
# Driver Code
if __name__ == '__main__':
# Let us create the graph shown
# in above diagram
graph = [[0, 4, 2, 6, 5],
[INF, 0, 4, 2, 5],
[INF, INF, 0, 4, 3],
[INF, INF, INF, 0, 3],
[INF, INF, INF, INF, 0]]
start = 0
steps = 3
nearest_dist, nearest_target = nearest_in_k_steps(graph, start, steps)
print(f"Node {nearest_target} is the nearest {steps}-step neighbor of {start}: distance = {nearest_dist}")
请注意,有几份印刷品只是为了帮助您了解代码的工作原理。
我想使用 k
条边从 source(u) 找到最短路径。这个 solution 似乎有效,但它搜索具有 k
条边的路径到给定节点 v
。如果 k
边在到达 v
之前被覆盖怎么办?我只想要 u
覆盖 k
边的所有路径的最短路径。不需要达到 v
。
上面的代码 link:
# 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, 4, 2, 6, 5],
[INF, 0, 4, 2, 5],
[INF, INF, 0, 4, 3],
[INF, INF, INF, 0, 3],
[INF, INF, INF, INF, 0]]
u = 0
v = 4
k = 3
print("Weight of the shortest path is",
shortestPath(graph, u, v, k))
您或许可以修复该代码(完全不传入或查看 v
- 见下文)。但我建议简单地修改 Dijkstra 的算法,最多从起始节点探索 3 条边。 Dijkstra 从头开始找到所有 shortest-length 条路径。当路径到达其第三个边缘时只需停止它(这将要求您除了保持距离外还保持 edge-counts)。
修改上面的代码也可以,但肯定会更慢,因为除非图形是树,否则您将多次查看每条边。
INF = 999999999999
def nearest_in_k_steps(graph, u, k):
print(f"Entering {u}, {k} steps remaining")
V = len(graph)
# Base case
if k == 0:
return 0, u
# Initialize result
best_dist = INF
best_target = None
# Go to all adjacents of u and recurse
for i in range(V):
if graph[u][i] != INF and u != i:
candidate_dist, candidate_target = nearest_in_k_steps(graph, i, k - 1)
candidate_dist += graph[u][i]
if candidate_dist < best_dist:
print(f"Hmm, path via {i} (d={candidate_dist}) is better than via {best_target} (d={best_dist})")
best_dist = candidate_dist
best_target = candidate_target
print(f"Returning from {u}, {k} steps remaining: d={best_dist} to {best_target}")
return best_dist, best_target
# Driver Code
if __name__ == '__main__':
# Let us create the graph shown
# in above diagram
graph = [[0, 4, 2, 6, 5],
[INF, 0, 4, 2, 5],
[INF, INF, 0, 4, 3],
[INF, INF, INF, 0, 3],
[INF, INF, INF, INF, 0]]
start = 0
steps = 3
nearest_dist, nearest_target = nearest_in_k_steps(graph, start, steps)
print(f"Node {nearest_target} is the nearest {steps}-step neighbor of {start}: distance = {nearest_dist}")
请注意,有几份印刷品只是为了帮助您了解代码的工作原理。