Shortest Paths

Dijkstra's Algorithm:

1) Label the initial vertex as 0

2) Box this number (permanent label)

3) Label each vertex connected to the initial vertex with its distance (temporary label)

4) Box the smallest number

5) From the vertex, consider the distance to each connected vertex

6) If a distance is less than the one already indicated at this vertex, cross out the old distance and write in the new distance. If there is no distance at the vertex, write down the new one. Do not make any changes if the number already indicated at this vertex is less than the new distance. 

7) Repeat Step 4 until the destination vertex is boxed.

Additional Information:

Graphs -

Structures made up of "vertices" and "edges."

Simple Graph

One that has a set of vertices that is not empty and a set of undirected edges linking those vertices. It also has no multiple edges or loops.

Directed Graph

One that has directed edges linking its vertices to a non-empty set of vertices.

Connected graph  

Contains arrows or lines.

Disconnected Graph 

Has a vertex that lacks any arrows or lines.

Degree -

It is the number of edges that cross it in an undirected graph.