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;
}
}
}
