图的最短路径算法

//最小起始边
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)  //有负权值会失效
{size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] = 0;pPath[srci] = srci;vector<bool> S(n,false);//已经确定最短路径的顶点集合for(size_t j = 0;j<n ;j++){//选最短路径的顶点更新其他路径int u = 0;W min = MAX_W;for (size_t i = 0; i < n; i++){if (S[i] == false && dist[i] < min){u = i;min = dist[i];}}S[u] = true;//更新u连接v srci->u  u->v  srci->vfor (size_t v = 0; v < n ; v++){if (S[v]==false &&_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]){dist[v] = dist[u] + _matrix[u][v];pPath[v] = u;}}}
}void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
{size_t srci = GetVertexIndex(src);size_t n = _vertexs.size();for (size_t i = 0; i < n; i++){if (i != srci){vector<int> path;//找出i顶点的路径size_t parent = i;while (parent != srci){path.push_back(parent);parent = pPath[parent];}path.push_back(srci);reverse(path.begin(), path.end());for (auto e : path){cout << _vertexs[e] << "->";}cout <<"权值和："<< dist[i] << endl;}}
}bool Bellman_ford(const V&src , vector<W>&dist , vector<int> & pPath)  //找终止边  解决不了负权回路
{size_t n = _vertexs.size();size_t srci = GetVertexIndex(src);dist.resize(n, MAX_W);//记录srci 其他顶点最短路径权值数组pPath.resize(n, -1); // 记录srci 其他顶点最短路径父顶点数组dist[srci] = W();//先更新srci->srci为缺省值for (size_t k = 0; k < n; k++)  //i->j暴力更新k次  总体最多更新n轮{bool updata = false;for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){updata = true;dist[j] = dist[i] + _matrix[i][j];pPath[j] = i;}}}if (updata == false) //没更新就退出 不需要走了{break;}}for (size_t i = 0; i < n; i++) //还能更新就是带负权回路{for (size_t j = 0; j < n; j++){if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){return false;}}}return true;
}void floyd( vector<vector<W>>& vvdist, vector<vector<int>>& vvpPath) //多源最短路径 任意两点
{size_t n = _vertexs.size();vvdist.resize(n);vvpPath.resize(n);for (size_t i = 0; i < n; i++){vvdist[i].resize(n, MAX_W);vvpPath[i].resize(n, -1); // n行}//直接相连的边更新一下for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (_matrix[i][j] != MAX_W){vvdist[i][j] = _matrix[i][j];vvpPath[i][j] = i;}if (i == j){vvdist[i][j] = W();}}}//最短路径的更新 i->j 中间可能经过k个顶点最多//把所有点都作为中间点 k作为中间点 是任意点 去更新i->jfor (size_t k = 0; k < n; k++){for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (vvdist[i][k] != MAX_W && vvdist[k][j] != MAX_W && vvdist[i][k] + vvdist[k][j] < vvdist[i][j])//已经有路径{vvdist[i][j] = vvdist[i][k] + vvdist[k][j];//找跟j相连的结点//如果k直接和j相连 vvpath[k][j] = k//如果k不和j相连 k->..x->j  vvpath[k][j]=xvvpPath[i][j] = vvpPath[k][j];}}}}// 打印权值和路径矩阵观察数据for (size_t i = 0; i < n; ++i){for (size_t j = 0; j < n; ++j){if (vvdist[i][j] == MAX_W){//cout << "*" << " ";printf("%3c", '*');}else{//cout << vvDist[i][j] << " ";printf("%3d", vvdist[i][j]);}}cout << endl;}cout << endl;for (size_t i = 0; i < n; ++i){for (size_t j = 0; j < n; ++j){//cout << vvParentPath[i][j] << " ";printf("%3d", vvpPath[i][j]);}cout << endl;}cout << "=================================" << endl;
}