Dijkstra's_algorithm(DA)

戴克斯特拉算法Dijkstra's algorithm(DA)

What:

Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Why:

Advantages of WA:

1. Once it has been carried out you can find the least weight path to all permanently labelled nodes.
2. You don’t need a new diagram for each pass.
3. Dijkstra’s algorithm has an order of n2 so it is efficient enough to use for relatively large problems.

Disadvantages of WA:

1. The major disadvantage of the algorithm is the fact that it does a blind search there by consuming a lot of time waste of necessary resources.
2. Another disadvantage is that it cannot handle negative edges. This leads to acyclic graphs and most often cannot obtain the right shortest path.

How:

A sample had been written in DA.py.

References:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
https://blog.csdn.net/johnjim0/article/details/109156772
http://cs.indstate.edu/~rjaliparthive/dijkstras.pdf