Pros and cons of dijskatra's and Prim's algorithm | SoloLearn: Learn to code for FREE!

-1

Pros and cons of dijskatra's and Prim's algorithm

12/26/2017 5:11:24 AM

Chaitanya

2 Answers

New Answer

+6

Dijkstra's Algorithm PRO 1)Uninformed algorithm Dijkstra is an uninformed algorithm. This means that it does not need to know the target node beforehand. For this reason it's optimal in cases where you don't have any prior knowledge of the graph when you cannot estimate the distance between each node and the target. 2)Good when you have multiple target nodes Since Dijkstra picks edges with the smallest cost at each step it usually covers a large area of the graph. This is especially useful when you have multiple target nodes but you don't know which one is the closest. CON Fails for negative edge weights If we take for example 3 Nodes (A, B and C) where they form an undirected graph with edges: AB = 3, AC = 4, BC=-2, the optimal path from A to C costs 1 and the optimal path from A to B costs 2. If we apply Dijkstra's algorithm: starting from A it will first examine B because it is the closest node. and will assign a cost of 3 to it and therefore mark it closed which means that its cost will never be reevaluated. This means that Dijkstra's cannot evaluate negative edge weights.

+1

Prim's algorithm Advantages Simple Disadvantages Time taken to check for smallest weight arc makes it slow for large numbers of nodes Difficult to program, though it can be programmed in matrix form.