answersLogoWhite

0


Best Answer

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.

User Avatar

Wiki User

15y ago
This answer is:
User Avatar
More answers
User Avatar

Wiki User

14y ago

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.

This answer is:
User Avatar

User Avatar

Wiki User

15y ago

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.

This answer is:
User Avatar

User Avatar

Wiki User

9y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

10y ago

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.

This answer is:
User Avatar

User Avatar

Wiki User

14y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

13y ago

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

This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: What is the difference between dijkstra and kruskal's algorithm?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Related questions

What is Dijkstra's algorithm?

Dijkstra's algorithm is used by the OSPF and the IS-IS routing protocols. The last three letters in OSPF (SPF) mean "shortest path first", which is an alternative name for Dijkstra's algorithm.


What is the Dijkstra's algorithm?

Dijkstra's algorithm has importance when you are trying to find the shortest path between two points. It's used in the computer networking field where routing protocols, like OSPF, uses it to find the shortest path between routers. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


What is the difference between Dijkstra's algorithm and Floyd's algorithm?

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. FloydSlow as compared to Dijkstra.


What are the advantages and disadvantages of dijkstra scholten algorithm versus bellman-ford algorithm?

The only difference between the two of these algorithm's is the person who invented the steps to solving the problems. The disadvantage to both of these are that they are very complex and hard to solve. The advantage is that using these methods can solve math problems that were unsolvable before this strategy was founded.


What is the difference between AES Rijndael symmetric algorithm encryption and a hash algorithm?

678


What is difference between lemma and algorithm?

A Method that used to be a comouter to soultion of promlems is called algorithm.


What is the difference between an algorithm and a computer program?


What is the difference between procedure and algorithm?

A procedure can go on forever.Where as an Algorithm, will eventually terminate and will have each step precisely defined.


Difference between greedy algorithm and dynamic programming?

the basic difference between them is that in greedy algorithm only one decision sequence is ever generated. where as in dynamic programming many decision sequences are generated.


Difference between Bresenham and midpoint circle drawing algorithm?

what is difference between mid-point and bresenhams circle algorithm what is difference between mid-point and bresenhams circle algorithm bresenhams circle algorithm results in a much more smoother circle,comparred to midpoint circle algorithm..In mid point,decision parameter depends on previous decision parameter and corresponding pixels whereas in bresenham decision parameter only depends on previous decision parameter...


What is the difference between an algorithm and flow chart WITH examples?

An algorithm is a method of solving a problem. A flow chart is a tool for visualizing algorithms.


What is the difference between advanced encryption algorithm and encryption algorithm?

People have developed many encryption algorithms. One particular encryption algorithm is the Rijndael algorithm, usually called the AES or Advanced Encryption Standard.