Tuesday, October 28, 2014

DIJKSTRA'S ALGORITHM with example.


Edsger Wybe Dijkstra in 2002
Born11 May 1930
Rotterdam, Netherlands
Died6 August 2002 (aged 72)
Nuenen, Netherlands
FieldsComputer science
Institutions

Known for
Notable awards
               Dijkstra's algorithm runtime                 Dijkstra's algorithm. It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

                                                                                                                                                                         Illustration of Dijkstra's algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the "tentative" set. Filled nodes are visited ones, with color representing the distance: the greener, the farther. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0.

Dijkstra's Algorithm

AIM: Implement Dijkstra’s algorithm to compute the Shortest path through graph.

DESCRIPTION: 

Dijkstra’s algorithm solves the simple source shortest paths problem on a weighted, directed graph. 

G=(V,E) for the case in which all weights are non negative. 

The algorithm repeatedly selects the vertex v belong s to v-s with the minimum shortest path estimate add ---

ALGORITHM: 

- Take a weighted, directed graph and take number of vertices. 

- Next take the weights between the states. 

- Start with the source vertex and identify the shortest path. 

- Repeat the above process for all the vertices repetitively until the destination is reached. 

- Display the shortest path from the source to destination. 


 OUTPUT:-
 Enter the number of nodes:4

 Enter the cost matrix:
0 3 23 0
3 0 2 0
23 2 0 5
0 0 5 0

 Enter the source node:1

 Enter the destination node:4

 Shortest path:
1->4,cost=10




No comments:

Post a Comment