python-3.x - 连接的元组对之间的最短路径

Question

我是这方面的新手，我会非常乐意提供任何帮助......我有一个元组列表，我必须找到连接的元组对之间的最短路径。例如，我有一个名为 pairs = [(1,2),(2,4),(1,3),(3,1),(4,3)] 的列表，我必须找到最短路径：

1 to 2, 1 to 3 and 1 to 4
2 to 1, 2 to 3 and 2 to 4
3 to 1, 3 to 2 and 3 to 4

在这个列表对中，如果我搜索 1 到 3 之间的联系，我必须得到可能的结果：

1) (1,3) 
2) (1,2)-(2,4)-(4,3)

当然最短的是第一个 - (1,3)

谢谢...

Answer 1

如果您只搜索两个数字之间的最短路径（我们称它们为节点）并且它们之间的边长度为 1，则可以使用BFS，如果它们有其他距离，则可以使用Dijkstra。由于两者都是图算法，您可能需要稍微更改它们，因为您只有一个边列表，而不是图结构。

Answer 2

使用BFS解决这样的未加权图中的最短路径问题。

伪代码：

Create Queue q;
push into q starting node and mark distance to starting node as 0.
while(q is not empty){
 get n : first elemnt in the queue
 get all connected nodes to n that are not yet visited and push them to the queue:
 mark the distance to those node as the distance to n + 1.
}

示例：假设您的起始节点是 1。

您在图中的连接：

   1->2,  1->3,  1->4
   2->1,  2->3,  2->4
   3->1,  3->2,  3->4

设置一个访问过的布尔数组：visited 4 = {false,false,false,false}，距离数组 dist 4 = {inf,inf,inf,inf} 和父数组 = {-1,-1,-1, -1}。

现在将节点 1 推入队列 Q，将其距离设置为 0，将父节点设置为 1，然后开始：

迭代 1 状态：

Queue = {1}
Dist = {0,inf,inf,inf}
visited= {true,false,false,false}
parent= {1,-1,-1,-1}

迭代 2：

队列中唯一的节点是 1，您选择它并将它们的邻居推送到队列中，它们是节点：2、3、4。更新他们的距离

Queue = {2,3,4}
Dist = {0,1,1,1}
visited= {true,false,false,false}
parent= {1,1,1,1}

依此类推，直到你得到一个空队列。（意味着您已经访问了所有节点）。

在这个例子中，你会看到到节点 3 的距离是 Dist 3 = 1，这个节点的父节点是 parent 3 = 1（如果你想重建路径）。

有关更多信息，请检查BFS以及 Python 中的实现：Python BFS DFS或此

Answer 3

def components_pairs(pairs):

    components = []

    for v1, v2 in pairs:
        for component in components:
             if v1 in component or v2 in component:
                 component.add(v1)
                 component.add(v2)
                 break
        else:
             components.append({v1, v2})

    return components

pairs = [(1,2),(1,3),(2,4),(3,1),(4,3)]

print(components_pairs(pairs))

Answer 4

这是旅行商问题。您可以使用遗传算法，它将以最低的操作成本为目标。问候。