最短路径之迪杰斯特（Dijkstra）与佛洛依德（Floyd）算法

最短路径之迪杰斯特（Dijkstra）与佛洛依德（Floyd）算法

求图中最短路径，可以依据图论中知识得到相应的最短路径知识，也有很详细的方法介绍，下面是以c++代码编程实现。

以矩阵形式表示图中权值

1 迪杰斯特（Dijkstra）

//迪杰斯特最短路径算法
template<typename T>
void minTreePaths<T>::minTreeDikjstra(vector<vector<int>> &mTree, int v0)
{T n = mTree.size();vector<T> w = mTree[v0];vector<T> final(n, 0);vector<T> node(n, 0);final[v0] = 1;//v0-v0已访问T min, k;for (int i = 1; i < n; i++){min = INT_MAX;for (int j = 0; j < n; j++){if (!final[j] && w[j] < min){min = w[j];k = j;}}final[k] = 1;//将已确认为最短路径顶点置1for (int m = 0; m < n; m++){//更新k到其它顶点最小权值if (!final[m] && (min + mTree[k][m] < w[m])){w[m] = min + mTree[k][m];node[m] = k;}}}
}

2 佛洛依德（Floyd）动态规划思想

template<typename T>
void minTreePaths<T>::minTreeFloyd(vector<vector<int>> &mTree, int v0)
{vector<vector<int>> w = mTree;vector<vector<int>> path(n, vector<int>(n, 0));//节点路径int n = mTree.size();for(int i = 0;i < n;i++)for (j = 0; j < n; j++){path[i][j] = j;}for(int i = 0;i < n;i++)for(int j = 0;j < n;j++)for (int t = 0; t < n; t++){if (w[j][t] > w[j][i] + w[i][t]){w[j][t] = w[j][i] + w[i][t];path[j][t] = path[j][i];}}
}