the shortest path dijkstra

What’s the Shortest Path?

The shortest path algorithm aims to solve a problem like this,“ Give you a directed weighted graph(or undirected graph,it doesn’t matter),how to calculate the shortest path from point A to point B “

How to Solve it ?

To solve this problem,I want to talk about the dijkstra algorithm,this algorithm has a premise,that’s all the edge weight must be a positive number. I will explain for it soon.

This algorithm work as beblow:

0, init the distance array,make d[A]=0,and d[others]=INF(A is the start point)
1, push A to a set S.
2, from the set S choose a vertex V which V is the most nearest to A,that's the d[V]=min{d[S]},and    V has not done the process 3
3, update all the vertexes which connected by V,push these points to the S,and mark the V is done.
4,repeat the 2 and 3 until all the points are done.

From the above processes we can see that this algorithm choose the point which is nearest to the start point,hence,it’s a greedy algorithm.

Why it’s correct?

Consider that D is the point we want to calculate,and B,C are the points which we have worked out.

the d[D] must be equal to min{d[B]+BD,d[C]+CD},that’s the minimum path from A to D must be equal to one of the neighboring points’ minimum path plus a edge weight.

How to code it ?

the problem click here

[the code click here ]

the shortest path tree

the shortest path graph