Dijkstra's Algorithm

graph-theory

Definition

Dijkstra's Algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest paths between two vertices in a network.

The weight of an edge sequence $e_1,e_2,\dots ,e_k$ is given by:

$$w(\{e_1,e_2,\dots ,e_k\})=\sum _{j=1}^{k}w(e_j)$$

where $w(e_j)$ is a non-negative weight function, $w:E\to {\mathbb{R}}_{\ge 0}$.

Algorithm: Let $q\in V$ be the source vertex and $s\in V$ be the sink vertex:

todo