Generate number of edges between two nodes

StackOverflow https://stackoverflow.com/questions/9389086

Question

I generated this Minimum Spanning Tree using Kruskal algorithm and I have a hard time generating paths between two nodes. Can someone help me with pseudocode? I tried using Adjacency List and Adjaceny matrix

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------
Was it helpful?

Solution

If you just want any path between two nodes, a Breadth First Search would do, and would generate the shortest path (because its a minimum spanning tree).

OTHER TIPS

Spanning trees, by definition, have no cycles (or loops), so at most you can only have one path (i.e. not "paths", plural) between two nodes.

Perhaps I'm not understanding the question. Are you trying to find how two given nodes are connected in your tree?

If so, it sounds to me like the simplest brute force on this, where you would just follow from one point along its possible edges, perhaps by pushing and popping possibilities from a stack, would be worst-case O(Edges) run time, which would be trivial compared to Kruskal's Algorithm. Do you need something faster?

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top