将 Dijkstra 算法从 Python3 转换为 CircuitPython (TI-Python)

Question

我正在为一个新的 TI-84 Python 版计算器编写 Python 代码。它们使用 CircuitPython 版本，对一些非常基本的功能提供有限支持。

这包括缺少的字典方法，例如 items() 和 values()。

我的 Dijkstra 算法的原始版本如下，随后是 TI-Python 中接近完整的版本。我在将最后两个 items() 实例转换为可行的替代方案时遇到问题。

nodes = ('A', 'B', 'C', 'D', 'E')
distances = {
    'A': {'B': 6, 'D': 1},
    'B': {'A': 6, 'C': 5, 'D': 2, 'E' :2},
    'C': {'B': 5, 'E': 5},
    'D': {'A': 1, 'B': 2, 'E': 1},
    'E': {'B': 2, 'C': 5, 'D': 1}}


unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'A' # the start node
currentDistance = 0
unvisited[current] = currentDistance

while True:
    # for the nodes adjacent to the current node.
    for neighbour, distance in distances[current].items():
        # ignore if already visited
        if neighbour not in unvisited:
            continue
        # calculate the total distance to this new node
        newDistance = currentDistance + distance
        # if this adjacent node has a lower distance
        if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
            # update distance to this new, lower distance
            unvisited[neighbour] = newDistance
    # add current node and distance from start to visited list
    visited[current] = currentDistance
    # Remove current node from unvisited list
    del unvisited[current]
    # if all nodes have been visited
    if not unvisited:
        # exit
        break
    # candidates for next node to visit
    print(unvisited.items())
        # print(node[1])
    candidates = [node for node in unvisited.items() if node[1]]
    print(candidates)
    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]

# print(visited)

print(dict(sorted(visited.items())))

TI-Python版本：

ns = ("A", "B", "C", "D", "E")
ds = {
    "A": {"B": 6, "D": 1},
    "B": {"A": 6, "C": 5, "D": 2, "E": 2},
    "C": {"B": 5, "E": 5},
    "D": {"A": 1, "B": 2, "E": 1},
    "E": {"B": 2, "C": 5, "D": 1}
}

un = {no: None for no in ns}
vi = {}
cn = "A"
cd = 0
un[cn] = cd

while True:
    for ne in sorted(ds[cn]):
        di = ds[cn][ne]
        if ne not in un:
            continue
        nd = cd + di
        if un[ne] is None or un[ne] > nd:
            un[ne] = nd
    vi[cn] = cd
    del un[cn]
    if not un:
        break
    cs = [no for no in un.items() if no[1]]
    cn, cd = sorted(cs, key=lambda x: x[1])[0]

print(dict(sorted(vi.items())))

有人可以解释一下如何重构 cs = [no for no in un.items() if no[1]] 和 print(dict(sorted(vi.items()))) 以便他们不需要 .items() 或 .values()。方法？

Answer 1

虽然.items()非常有用，但它相当于迭代键然后查找值。

for k in dict:
    v = dict[k]

相当于

for k, v in dict.items():

因此

的粗略重构

cs = [no for no in un.items() if no[1]]

将是：

cs = [[k, un[k]] for k in un if un[k]]

注意原文最好写成：

cs = [[k,v] for k, v in un.items() if v]

同样，

print(dict(sorted(vi.items())))

直接等同于：

print(dict(sorted([k, vi[k] for k in vi]))

但是恕我直言，这不是很可读。我会这样做：

print({k: vi[k] for k in sorted(vi.keys()})

将 Dijkstra 算法从 Python3 转换为 CircuitPython (TI-Python)

Converting Dijkstra's Algorithm from Python3 to CircuitPython (TI-Python)

python

dictionary

adafruit-circuitpython