假设S为已经求出的最短路径顶点的集合，而V是还未求出的最短路径的顶点的集合。

现用数学归纳法证明算法正确性：

1.已知当S中除了源点V0只有一个点v1时，可以证明V0到V1的路径一定是最短的。反证法证明：假设V0到V1的距离不是最短的，那么必定存在一个点Vx，有路径(V0,Vx,V1)是最短的。但这是不可能的，因为根据算法如果(V0,Vx,V1)的路径比(V0,V1)路径要短，那么算法就会选择x加入S中，而不会选择V1，这与已知条件矛盾，故假设不成立。

2.现证明当S除源点外有n个点，当加入除源点的第n+1个点即Vn+1时，源点V0到Vn+1的路径是最短路径，算法正确性即可得证。

3.根据假设条件，当前源点到顶点Vn,Vn+1以及V中剩余顶点的最短路径为D[n]。根据算法，当加入第n+1个顶点时，源点到Vn+1的最短路径只有两种可能：(V0,Vn+1)或者(V0,Vn,Vn+1)，即它的长度要么是V0到Vn+1的弧上的权值，要么是D[n]和从Vn到Vn+1的弧上权值之和，可以证明得到的路径一定是最短的。反证法证明：假设V0到Vn+1的最短路径上有一个顶点不在S中，则说明存在一条最短路径的终点不在S而长度比此路径要短。但这是不可能的，因为算法是按路径长度递增的次序来产生各最短路径的，故长度比此路径短的所有路径均已产生，它们的终点比定在S中，即假设不成立。

4.Dijkstra算法正确性得证。

备注：关于最短路径算法的使用问题，如果是无权图求最短路径优先采用广度优先算法（BFS）；如果是有权图则采用迪杰斯特拉算法。