Shortest path between connected pairs of tuples

Question

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

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)

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

Thanx...

are the path weighted?? mean from 1 to 2 is it the same distance as from 1 to 3 ??? @user2923389 — yahya el fakir, May 05 '15 at 09:59
no there are no weights... 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) and of course the shortest one is the first one - (1,3) and output of my program has to be 1. For instance if the shortest path for 1 to 3 was (1,2)-(2,4)-(4,3), then output of my program has to be 3 because there are three pairs — user2923389, May 05 '15 at 10:04
Can you add language tag? Or it it's too general, maybe `algorithm` tag or something. At first it looks like Python, however, we can't read your mind and adding the tag can help you get the best answer. — Adalee, May 05 '15 at 10:09

score 1 · Answer 1 · answered May 05 '15 at 10:14

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.

score 0 · Answer 2 · edited May 23 '17 at 11:51

Use BFS for solving a shortest path problem in an unweighted graph like that.

Pseudo code :

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.
}

Example : assuming your start node is 1.

connections you have in the graph :

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

Set a visited array of boolean : visited 4 = {false,false,false,false}, and a distance array dist4 = {inf,inf,inf,inf} and parent array = {-1,-1,-1,-1}.

now push Node 1 into the queue Q, set it distance to 0 and parent to 1 then start:

Iteration 1 state:

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

Iteration 2 :

the only node in the Queue is 1, you pick it and push their neighbors to Queue which are nodes: 2,3,4. update their distances

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

and so on until you get an empty queue. (means you have visited all the nodes).

in this example you'll see that the distance to node 3 is Dist3 = 1, the parent of this node is parent3 = 1 (in case you want to reconstruct the path).

for more information check BFS and also an implementation in Python : Python BFS DFS or this

thanx,but as i said that i am new in this i would rather not use algorithms like this...instead i wrote code that returns all connected nodes...do you think if it is possible using this to find the shortest path — user2923389, May 05 '15 at 11:13
Hmmm, altough i think that BFS is pretty easy implementation, if you dont want to use it, you can write a recursive solution and brute force all the paths *Which if your the number of nodes you have is > 20* would not work :/ @user2923389 — yahya el fakir, May 05 '15 at 13:21

user2923389 · Answer 3 · 2015-05-05T11:23:15.127

0

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))

edited May 05 '15 at 11:23

answered May 05 '15 at 11:15

user2923389

141
1
14

score -3 · Answer 4 · answered May 05 '15 at 10:07

-3

This is Travelling salesman problem. You can use genetic algorithm, it will goal a goal with the lowest cost of operations. Greetings.

answered May 05 '15 at 10:07

PianistaMichal

305
1
2
14

As is stated in the link you provided, traveling salesman problem is something *completely* different. Also, it's NP-hard, which basically means you have no general effective algorithm to solve the problem. – Adalee May 05 '15 at 10:19

Shortest path between connected pairs of tuples

4 Answers4

Linked