连接的元组对之间的最短路径 [英] Shortest path between connected pairs of tuples

问题描述

我是新来的，对于任何类型的帮助，我都非常乐意……我有一个元组列表，我必须找到连接的元组对之间的最短路径.例如，我有一个名为pairs = [(1,2),(2,4),(1,3),(3,1),(4,3)]的列表，我必须找到最短路径:

I'm new at this and i would be really greatfull for any kind of help...I have a list of tuples and I have to find shortest path between connected pairs of tuples. For example, I have list called pairs = [(1,2),(2,4),(1,3),(3,1),(4,3)] and i have to find shortest path for:

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 之间的联系，我必须得到可能的结果:

In this list pairs, if I search for connection between 1 to 3, I have to possible outcomes:

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

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

and of course the shortest one is the first one - (1,3)

谢谢...

推荐答案

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

If you only search for the shortest path between two numbers (lets call them nodes) and the length of the edges between them is 1, you can use BFS, if they have some other distance, you can use Dijkstra. Since both are graph algorithms, you may need to change them a little since you have only a list of edges, not graph structure.

这篇关于连接的元组对之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！