Shortest Path
Task:
Find the shortest path between two nodes (points).
Solution:
The most famous solution for this problem was first proposed by Dijkstra. Generally, his solution is the most efficient and used in most cases.
Algorithm:
 Set the distance to source node to 0, and the distances to all other nodes to infinity.
 Among all unprocessed nodes find the one that has the minimum distance to it yet found. Let this node be i. If
i is the destination (end) node then exit because the shortest path from source to destination has been found. Otherwise
mark it as processed and go to point 3.
Note: If distances to all unprocessed nodes are equal to Infinity then no path from source to destination node exists.
 Look at each unprocessed neighbor j of node i. If the shortest distance to j is
greater than the shortest distance to i + the cost of the edge between these 2 nodes, then update the shortest distance/path
to j with this one and mark that it has been reached from i.
Go back to point 2.
Pseudocode:
# N  number of nodes
# weight(i,j)  weight of the edge from node i to j ; equal to infinity if such an edge doesn't exist
# dist(i)  the shortest path from source node to i
# parent(i)  node that precedes i in a shortest path, used to reconstruct the shortest path
# initialize all values
For i = 1 to N
dist(i) = infinity
processed(i) = false
parent(i) = null
End For
dist(source) = 0
While (not all nodes have been processed)
If (distances to all unprocessed nodes are equal to infinity) Then
no path from source to destination node exists
Exit
End If
Let i be an unprocessed node for which dist(i) is the smallest among all unprocessed nodes.
If i = destination Then Exit While # shortest path from source to
destination has been found
Set processed(i) = true
For Each unprocessed node j # i.e. for which processed(j) = false
If dist(i) + weight(i,j) < dist(j) Then
# a shorter path from source node to j has been found ; update it
dist(j) = dist(i) + weight(i,j)
parent(j) = i
End If
End For
End While
# the length of the shortest path is thus dist(destination)
# path reconstruction is given below
Set i = destination
While i != source
Append i to the beginning of the currently constructed path
i = parent(i)
End While
Append source to the beginning of the path
Complexity:
In average each of N nodes is processed, and for each all of its neighbors are updated in O(N). Thus the complexity is O(N^{2}).
Restrictions:
This algorithm doesn't work for graphs that have negative edges. For these you should use BellmanFord algorithm, that runs in O(NM),
where M is the number of edges.
Optimizations:
 For sparse graphs a complexity of O(NlogN) may be obtained. For this purpose a heap is used to store the shortest
distances to nodes, and neighbors of each node are stored in lists. In this way the unprocessed node with the minimum distance is found
in logN and the update of each node is also done in logN.
Providing that the graph is sparse, each node has few neighbors and thus the average complexity is O(NlogN).
 If edges have no costs then a Breadth First Search (BFS) algorithm can be applied to find the shortest path. It would run substantially
faster, especially for graphs that have structures similar to mazes, tables, where each point has few neighbors.
Extensions:
If the above code is run until all nodes are processed (or until no unprocessed node is reachable) then we will get the shortest paths
from source point to all other points (those that are reachable from it).
Sample Execution:
Applications:
This is probably the most used graph algorithm. It may be applied in situations where the shortest path between 2 points is needed. Examples
of such applications would be:
 Computer games  finding the best/shortest route from one point to another.
 Maps  finding the shortest/cheapest path for a car from one city to another, by using given roads.
 May be used to find the fastest way for a car to get from one point to another inside a certain city. E.g. satellite navigation system
that shows to drivers which way they should better go.
A maze 
The shortest path between the corners of the maze 
