1. Dijkstra算法（迪杰斯特拉算法）
所求的是，某一个顶点到图中各点的最短路径。
算法基本思路
- 找到离顶点最近且未标记的点，此时所得的路径便是这两点最短的距离（当前两点路径已经是全图最近，若再经过别的点的中转，必然绕远了）
- 标记最近点
- 刷新所有点离开始顶点的距离，重复第一步
for (v = 0; v < G.numVertexes; y++)
{
//初始化各点与源点的距离，final用于保存各点是否找到最短路径
final[v] = 0;
D[v] = G.matirx[V0][v];
P[v] = 0;
}
//
for (v = 1; v < G.numVertexes; v++)
{
//遍历所有结点，找到离源点最近，且还未找到最短路径的点
min = INFINITY;
for (w = 0; w < G.numVertexes; w++)
{
if (!final[w] && D[w] < min)
{
k = w;
min = D[w];
}
}
final[k] = 1;//把顶点k标记，已经找到最短路径
for (w = 0; w < G.numVertexes; w++)
{
//k点最短路径找到后，更新没找到最短路径的顶点与源点的距离
if( !final[w] && (min + G.matirx[k][w] < D[w]))
{
D[w] = min + G.matirx[k][w];
P[w] = k;
}
}
}
2. Floyd算法（弗洛伊德算法）
不断地通过尝试添加中转点，刷新两个顶点之间的距离，保存最短的。最终找到所有顶点到所有顶点的最短路径。
为此，需要两个变量用以保存，一个是两点之间的距离，一个是两点之间离终点最近的一个中转点。
for (v = 0; v < G.numVertexes; ++v)
{
for (w = 0; w < G.numVertexes; ++w)//遍历所有顶点对
{
D[v][w] = G.matirx[v][w];//两点距离，初始化为邻接矩阵的距离
P[v][w] = w;//路径直接保存为w
}
}
for (k = 0; k<G.numVertexes; ++k)
{
for (v = 0; v < G.numVertexes; ++v)
{
if ( D[v][w] > D[v][k] + D[k][w])
{
//如果新的中转点使得两点距离变短，更改两点距离及路径
D[v][w] = D[v][k] + D[k][w];
P[v][w] = k;
}
}
}
