在有向加权图中，有效地找到穿过节点 X 的两个节点 A 和 B 之间的最短路径的成本

Question

我是初学者，仍在掌握路径算法的概念。我们的教授给了我们这个问题，哪个解决方案将由在线评委评估：

我得到以下信息：

节点数L（每个节点以数字命名，从1开始索引）
- 2 <= L <= 1000
从一个节点到另一个节点的有向边R，以及边的成本C
- 0 <= R <= L * sqrt(L)
- 1 <= C <= 100
- 边数与节点数一起给出，以便轻松收集有向边。
- 没有负成本。
源节点A
目的节点B
遍历的节点X

我需要找到从 A 到 X 到 B 的最短路径的成本。

我的代码运行如下：

获取输入。
生成图的邻接表。
获取 A、X 和 B。
获取A和X之间最短路径的成本ax。
获取X和B之间最短路径的成本xb。
从A到X到B的最短路径的成本axb是ax + xb。

裁判判定本题超过1秒的时限。有没有办法改进它并使其更有效率？

我考虑过将 X 设为源节点，但该图是有向的，取消定向会产生错误的结果。
我考虑过检查 A 和 X 之间的路径是否存在，然后是 X 和 B，但似乎对性能的影响可以忽略不计。
我也考虑过“限制”图表，使其只包含 A 和 B 之间通过 X 的路径，但我不知道如何以最有效的方式做到这一点.
我试过应用 this idea，但只是运行变长了。
我的教授说 A* 对于他给我们的问题来说太过分了，但如果我想出一个启发式算法，也许我会考虑使用它。
我尝试了 Floyd-Warshall 算法，但它使代码消耗更多的时间和内存 - 但有些东西告诉我这个算法可以优化：

def shortestPath(dist, i, j, k): # My first try in applying the Floyd-Warshall Algorithm

    for k in range(len(dist)):
        for i in range(len(dist)):
            for j in range(len(dist)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

# Graph construction and algorithm application:
    .
    .
    .
    # generate adjacency list of the graph
    graph = [[math.inf for node_x in range(nodes)] for node_y in range(nodes)]
    next = [[None for node_x in range(nodes)] for node_y in range(nodes)]
    for node in range(nodes):
        graph[node][node] = 0

    for edge in range(edges):
        node_a, node_b, cost = input().split()
        node_a = int(node_a) - 1
        node_b = int(node_b) - 1
        cost = eval(cost)
        graph[node_a][node_b] = cost
        next[node_a][node_b] = node_b

    i, k, j = input().split()  # get source, traversed and destination node
    i = int(i) - 1
    j = int(j) - 1
    k = int(k) - 1
    shortestPath(graph, i, j, k)
    ikj = graph[i][j]

    if ikj == math.inf:  # path nonexistent if either ax or xb is infinite
        out.append("path nonexistent")
        continue
    else:
        out.append(ikj)

这是我的代码：

import heapq
import math


# tools start here

def dijkstra(G, S):
    pq = []
    costs = {v: math.inf for v in G}
    costs[S] = 0

    heapq.heappush(pq, (0, S))
    while pq:
        d_u, u = heapq.heappop(pq)
        for e in G[u]:
            v, w = e
            d_v = costs[v]
            if d_v > d_u + w:  # relaxation operation
                costs[v] = d_u + w
                heapq.heappush(pq, (d_u + w, v))
    return costs


# tools end here

t = int(input())  # get number of test cases
out = []  # initialize output array
for _ in range(t): # for each test case

    # get input
    nodes, edges = input().split()
    nodes = int(nodes)
    edges = int(edges)

    # generate adjacency list of the graph
    graph = {}
    for node in range(1, nodes + 1):
        graph[str(node)] = []

    for edge in range(edges):
        node_a, node_b, cost = input().split()
        cost = eval(cost)
        graph[node_a].append((node_b, cost,))

    a, x, b = input().split()  # get source, traversed and destination node

    ax = dijkstra(graph, a)[x]  # get shortest path cost from a to x
    xb = dijkstra(graph, x)[b]  # get shortest path cost from x to b

    axb = ax + xb  # add the path costs

    if axb == math.inf:  # path nonexistent if either ax or xb is infinite
        out.append("path nonexistent")
        continue
    else:
        out.append(axb)

[print(_) for _ in out]  # print output array

这是示例输入：

这是示例输出：

2
path nonexistent

Answer 1

我认为你的解决方案已经是最快的了。

如果您想从代码中获得更多运行时性能，我建议重新检查 A 和 X 之间的路径是否存在，然后是 X 和 B。

我还建议将您的 eval() 替换为 int()，因为考虑到您的问题的限制，假设检查它是否为 int 以外的任何东西会更慢。

最后，这很可能是一个在线判断，它接受打印输出的代码，因此在每个测试用例后立即输出答案。

希望对您有所帮助！

在有向加权图中，有效地找到穿过节点 X 的两个节点 A 和 B 之间的最短路径的成本

In a directed, weighted graph, efficiently find the cost of the shortest path between two nodes A and B that traverses through a node X

python

python-3.x

graph-theory

shortest-path

dijkstra