按路径长度递增的次序产生最短路径的算法。
大致思路：
求两顶点之间的最短路径，先一步步求出两点之间顶点的最短路径，基于已求出的最短路径的基础上，求得更远顶点的最短路径，最终得到结果。
Code:
#define MAXVEX 100
#define INFINITY 65535
typedef int Patharc[MAXVEX]; //用于存储最短路径下标的数组，其值代表结点前驱下标
typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短路径的权值和
/*Dijkstra算法，将有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]*/
/*P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v, w, k, min;
int final[MAXVEX]; //final[w]=1表示求得顶点v0至vw的最短路径
for (v = 0; v < G.numVertexes; v++) //初始化数据
{
final[v] = 0; //全部顶点初始化为未知最短路径状态
(*D)[v] = G.arc[v0][v]; //将与v0点有连线的顶点加上权值
(*P)[v] = 0; //初始化路径数组P为0
}
(*D)[v0] = 0; //v0至v0路径为0
final[v0] = 1; //v0至v0不需要求路径
//开始主循环，每次求得v0到某个v顶点的最短路径
for (v = 1; v < G.numVertexes; v++)
{
min = INFINITY; //当前所知离v0顶点的最近距离
for (w = 0; w < G.numVertexes; w++) //寻找离v0最近的顶点
{
if (!final[w] && (*D)[w] < min)
{
k = w;
min = (*D)[w]; //w顶点离v0顶点更近
}
}
final[k] = 1; //将目前找到的最近的顶点置为1
for (w = 0; w < G.numVertexes; w++) //修正当前最短路径及距离
{
//如果经过v顶点的路径比现在这条路径的长度短的话
if (!final[k] && (min + G.arc[k][w]) < (*D)[w])
{//说明找到了更短的路径，修改D[w]和P[w]
(*D)[w] = min + G.arc[k][w]; //修改当前路径长度
(*P)[w] = k;
}
}
}
}
时间复杂度：O(n^2)
