[go: up one dir, main page]
Scribd
Upload
9 views3 pages

Untitled Document

Uploaded by

024CSE DHARSHINI.A
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views3 pages

Untitled Document

Uploaded by

024CSE DHARSHINI.A
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Dijkstra's Algorithm

“Graphs are non-linear data structures representing the "connections"


between the elements. These elements are known as the Vertices, and the
lines or arcs that connect any two vertices in the graph are known as the
Edges. More formally, a Graph comprises a set of Vertices (V) and a set
of Edges (E). The Graph is denoted by G(V, E).”

● Dijkstra's algorithm finds the shortest path from one vertex to all
other vertices.
● It does so by repeatedly selecting the nearest unvisited vertex and
calculating the distance to all the unvisited neighboring vertices.
● Dijkstra's shortest path algorithm was invented in 1956 by the
Dutch computer scientist Edsger W. Dijkstra during a twenty
minutes coffee break, while out shopping with his fiancée in
Amsterdam.
● The reason for inventing the algorithm was to test a new computer
called ARMAC.
● Dijkstra's algorithm is often considered to be the most
straightforward algorithm for solving the shortest path problem.
● Dijkstra's algorithm is used for solving single-source shortest path
problems for directed or undirected paths.
● Single-source means that one vertex is chosen to be the start, and
the algorithm will find the shortest path from that vertex to all other
vertices.
● Dijkstra's algorithm does not work for graphs with negative edges.
● To find the shortest path, Dijkstra's algorithm needs to know which
vertex is the source.

Understanding the Working of Dijkstra's Algorithm


A graph and source vertex are requirements for Dijkstra's Algorithm. This
Algorithm is established on Greedy Approach and thus finds the locally optimal
choice (local minima in this case) at each step of the Algorithm.

Each Vertex in this Algorithm will have two properties defined for it:

1. Visited Property
2. Path Property

Let us understand these properties in brief.

Visited Property:
1. The 'visited' property signifies whether or not the node has been visited.
2. We are using this property so that we do not revisit any node.
3. A node is marked visited only when the shortest path has been found.

Path Property:
1. The 'path' property stores the value of the current minimum path to the
node.
2. The current minimum path implies the shortest way we have reached this
node till now.
3. This property is revised when any neighbor of the node is visited.

You might also like