3个项目的地图的最佳数据结构是什么

Question

假设有给定的值（原点、命运、距离）：

A ~ B = 5
B ~ C = 10
A ~ C = 20

我想找到从A到C的最短路径（在本例中是A->；B，B->；C）。你知道吗

存储/搜索这些值的最佳数据结构是什么？你知道吗

Answer 1

可以使用networkx表示加权图，然后使用 ^{}找到最短路径。你知道吗

示例：

#!/usr/bin/env python

import networkx as nx

G=nx.Graph()

G.add_edge('a','b',weight=5)
G.add_edge('b','c',weight=10)
G.add_edge('a','c',weight=20)

print(nx.dijkstra_path(G,'a','c'))

这将作为输出：

['a', 'b', 'c']

我认为dijkstra算法是解决从一个顶点到所有其他顶点的最短路径问题的最佳方法，至于复杂度，它是O（nlogn），其中n是顶点的个数。你知道吗

当然，最短路径算法只有在没有负圆的情况下才有效（最短路径问题没有意义…）。你知道吗