Dijkstra

A simple Dijkstra algorithm implementation in python.

3 Dict used:
1). graph: a dict to save all of the nodes and length between two neighbors.
2). costs: a dict to save the length from start node to current node. In the beginning, only neighbors of start node has the real cost, others will be +infinite.
3). parent: a dict to save the parent of all nodes. In the beginning, only neighbors of start node contains valid parent node, which is the start node. Others are initialized to empty.

1 list used:
node_list: a list to save all un-handled nodes

This algorithm is to iterate node_list, pop the node with shortest length to start node, and then iterate its neighbors, calculate the length from current node to the neighbor, if the length is less than current neighbor's length, update the costs and parent list, save the length as new costs, and update parent node of the neighbor as the current node.

when the node_list is empty, the algorithm end up, and at that time, value of node 'End' in the costs list is the shortest length, and we can get the path in the parent dict. Find the parent of nodes from 'End' to 'Start', should be the reverse order of path.

The key for this algorithm is that:

1. Costs list to save the length from start node to current node
2. Each node in costs list only be updated by its parent.