图表最短路径利润中的热带数学

Question

我尝试应用热带数学来加速最短路径算法。有人提到，公司将其用于路线规划系统。然而，我没有发现使用热带数学和使用布尔逻辑的常规数学在算法性能上有任何差异。我找不到任何有关此方法的具体实现的资源。如何使用此方法提高速度？提供一个示例算法来证明这种速度的提高。

我尝试以单线程和多线程方式测试我的热带优化算法。结果有时是相同的，但有时甚至比 Dijkstra 等常规最短路径算法更糟糕。我生成的所有样本堆栈的结果都是一致的。

Answer 1

好吧，我测试了这段代码——热带优化的 Dijkstra 算法——你知道吗？实际上，在我尝试的每一项测试中，它都比正常测试慢。不确定热带数学是否真的有优势:/

# Tropical:
import heapq

def dijkstra(graph, start):
    d = {v: float('inf') for v in graph}
    d[start] = 0
    pq = [(0, start)]
    while pq:
        dv, v = heapq.heappop(pq)
        if dv > d[v]:
            continue
        for u, w in graph[v].items():
            tw = d[v] + w
            if tw < d[u]: d[u], _ = tw, heapq.heappush(pq, (tw, u))
    return d

与我使用的标准库 Dijkstra 方法进行比较。