What is the difference between dijkstra and kruskal's algorithm?

Answer 1

Both of these functions solve the single source shortest path problem. The primary difference in the function of the two algorithms is that Dijkstra's algorithm cannont handle negative edge weights. Bellman-Ford's algorithm can handle some edges with negative weight. It must be remembered, however, that if there is a negative cycle there is no shortest path.

Answer 2

Dijkstra's algorithm is almost identical to that of Prim's. The algorithm begins at a specific vertex and extends outward within the graph, until all vertices have been reached. The only distinction is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to the current vertex. More simply, Dijkstra's algorithm stores a summation of minimum cost edges whereas Prim's algorithm stores at most one minimum cost edge.

Answer 3

Dijkstra's algorithm will find the shortest path between two vertices.

Kruskal's algorithm will find the minimum spanning tree connecting all the given vertices.

Basically, Dijkstra's will find a connection between two vertices, while Kruskal's will find a connection between and number of vertices.

Answer 4

Dijkstra doesn't support negative weight-age, Floyd support negative edges but no negative cycles. Dijkstra running time is v2 and Floyd has v3.Dijkstra is fast compared to Floyd, because only find the shortest path for single node. Floyd Slow as compared to Dijkstra.

Dijkstra's Algorithm

Notation:

Di = Length of shortest path from node 'i' to node 1.

di,j = Length of path between nodes i and j .

Algorithm

Each node j is labeled with Dj, which is an estimate of cost of path from node j to node 1. Initially, let the estimates be infinity, indicating that nothing is known about the paths. We now iterate on the length of paths, each time revising our estimate to lower values, as we obtain them. Actually, we divide the nodes into two groups ; the first one, called set P contains the nodes whose shortest distances have been found, and the other Q containing all the remaining nodes. Initially P contains only the node 1. At each step, we select the node that has minimum cost path to node 1. This node is transferred to set P. At the first step, this corresponds to shifting the node closest to 1 in P. Its minimum cost to node 1 is now known. At the next step, select the next closest node from set Q and update the labels corresponding to each node using :

Dj = min [ Dj , Di + dj,i ]

Finally, after N-1 iterations, the shortest paths for all nodes are known, and the algorithm terminates.

Principle

Let the closest node to 1 at some step be i. Then i is shifted to P. Now, for each node j , the closest path to 1 either passes through i or it doesn't. In the first case Dj remains the same. In the second case, the revised estimate of Dj is the sum Di + di,j . So we take the minimum of these two cases and update Dj accordingly. As each of the nodes get transferred to set P, the estimates get closer to the lowest possible value. When a node is transferred, its shortest path length is known. So finally all the nodes are in P and the Dj 's represent the minimum costs. The algorithm is guaranteed to terminate in N-1 iterations and its complexity is O( N2 ).

The Floyd Warshall Algorithm

This algorithm iterates on the set of nodes that can be used as intermediate nodes on paths. This set grows from a single node ( say node 1 ) at start to finally all the nodes of the graph. At each iteration, we find the shortest path using given set of nodes as intermediate nodes, so that finally all the shortest paths are obtained.

Notation

Di,j [n] = Length of shortest path between the nodes i and j using only the nodes 1,2,....n as intermediate nodes.

Initial Condition

Di,j[0] = di,j for all nodes i,j .

Algorithm

Initially, n = 0. At each iteration, add next node to n. i.e. For n = 1,2, .....N-1 ,

Di,j[n + 1] = min { Di,j[n] , Di,n+1[n] + Dn+1,j[n] }

Principle

Suppose the shortest path between i and j using nodes 1,2,...n is known. Now, if node n+1 is allowed to be an intermediate node, then the shortest path under new conditions either passes through node n+1 or it doesn't. If it does not pass through the node n+1, then Di,j[n+1] is same as Di,j[n] . Else, we find the cost of the new route, which is obtained from the sum, Di,n+1[n] + Dn+1,j[n]. So we take the minimum of these two cases at each step. After adding all the nodes to the set of intermediate nodes, we obtain the shortest paths between all pairs of nodes together. The complexity of Floyd-Warshall algorithm is O ( N3 ).

Answer 5

If you are interested in the details in how they work, you may want to consult the Wikipedia articles on both algorithms - or some other source. For example, an introductory course in algorithms. But briefly, the difference between the two is: Dijkstra's algorithm is faster. On the other hand, Bellman Ford's algorithm can handle negative "distances", which Dijkstra's algorithm can't handle. So, if there is a need to include negative distances in the calculation, the Bellman Ford algorithm should be used; if, on the other hand, there is no such requirement, Dijkstra's algorithm is usually preferable.

Answer 6

The only difference between two is that Bellman Ford is capable also to handle negative weights whereas Dijkstra Algorithm can only handle positives.

Answer 7

Floyd Warshall calculates shortest distance between nodes while Bellman Ford algorithm calculates shortest path distance from source node to other vertexes.