-2

I am very confused about when should I not use this algorithm.

I thought kruskal was used to find the shortest path however i came to know that it is not used to find the shortest path instead Minimum spanning tree. Therefore I became more confused like didn't the MST is used to find the minimum cost hence shortest path ? Since Prims' and Kruskal are used to find the same thing which is MST, then why not ask both topics where someone who has a better foundation clear that up to me.

Improve this question
4
  • Do not tag this as dsa. The dsa tag is for Digital Signature Algorithm. Commented Jan 13 at 14:19
  • If you only want to find the shortest path between two points, computing an MST is both insufficient (the shortest path between the two points may not be on the minimum spanning tree) and overkill (if the shortest path is on the MST, you don't necessarily need the entire spanning tree). Commented Jan 13 at 14:34
  • MST does not necessarily give you the shortest path. See cs.stackexchange.com/questions/18797/…, stackoverflow.com/questions/63203004/… and stackoverflow.com/questions/10448397/… for a start. Commented Jan 13 at 14:34
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. Commented Jan 13 at 23:20

1 Answer 1

Reset to default
0

To find the shortest path between two nodes in a graph where all the edges have zero or equal weight: use depth first searching. This is simple and fast and, if you avoid the recursive versions, able to handle the largest graphs ( millions of edges )

If the the graph edges have different weights, all positive, and you want to find the path with the least total weight then use the Dijkstra algorithm.

The minimum spanning tree algorithms are complex, slow, and are NOT guaranteed to find the shortest path. Do not use them.

By the way, the graph data structure is irrelevant here. All algorithms can use whatever data structure you choose ( adjacency matrix and adjacency list are the most popular ).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.