Search code examples
algorithmgraphgraph-algorithmminimum-spanning-treekruskals-algorithm

Generate number of edges between two nodes


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

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