Dijkstra's algorithm

Dijkstra's algorithm, named after its inventor, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.

Related Topics:
Computer scientist - Edsger Dijkstra - Algorithm - Shortest path problem - Directed graph - Edge

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For example, if the vertices of the graph represent cities and edge weights

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

represent driving distances between pairs of cities connected by a direct road,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Dijkstra's algorithm can be used to find the shortest route between two cities.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The input of the algorithm consists of a weighted directed graph G and a source vertex s in G. We will denote V the set of all vertices in the graph G. Each edge of the graph

Related Topics:
Vertices - Edge

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

is an ordered pair of vertices (u,v) representing a connection

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

from vertex u to vertex v. The set of all edges is denoted E.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Weights of edges are given by a weight

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

function w: E -> ; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The cost of an edge can be thought of as (a generalization of) the distance between those two vertices. The cost of a path between two vertices is the sum of costs of the edges

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~