the-shortest-road(4).rar_The Road

#define INFINITE 1000 // 最大值 #define MAX_VERTEX_COUNT 20 　　// 最大顶点个数 ////////////////////////////////////////////////////////////////////////// struct Graph { int arrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; // 邻接矩阵 int nVertexCount; 　　// 顶点数量 int nArcCount; 　　// 边的数量 }; void readGraphData( Graph *_pGraph ) { std::cout << "请输入顶点数量和边的数量: "; std::cin >> _pGraph->nVertexCount; std::cin >> _pGraph->nArcCount; std::cout << "请输入邻接矩阵数据:" << std::endl; for ( int row = 0; row < _pGraph->nVertexCount; ++row ) { for ( int col = 0; col < _pGraph->nVertexCount; ++col ) { std::cin >> _pGraph->arrArcs[row][col]; } } } void floyd( int _arrDis[][MAX_VERTEX_COUNT], int _arrPath[][MAX_VERTEX_COUNT], int _nVertexCount ) { // 先初始化_arrPath for ( int i = 0; i < _nVertexCount; ++i ) { for ( int j = 0; j < _nVertexCount; ++j ) { _arrPath[i][j] = i; } } ////////////////////////////////////////////////////////////////////////// for ( int k = 0; k < _nVertexCount; ++k ) { for ( int i = 0; i < _nVertexCount; ++i ) { for ( int j = 0; j < _nVertexCount; ++j ) { if ( _arrDis[i][k] + _arrDis[k][j] < _arrDis[i][j] ) { // 找到更短路径 _arrDis[i][j] = _arrDis[i][k] + _arrDis[k][j]; _arrPath[i][j] = _arrPath[k][j]; } } } } } void printResult( int _arrDis[][MAX_VERTEX_COUNT], int _arrPath[][MAX_VERTEX_COUNT], int _nVertexCount ) { std::cout << "Origin -> Dest Distance Path" << std::endl; for ( int i = 0; i < _nVertexCount; ++i ) { for ( int j = 0; j < _nVertexCount; ++j ) { if ( i != j ) // 节点不是自身 { std::cout << i+1 << " -> " << j+1 << "\t\t"; if ( INFINITE == _arrDis[i][j] ) // i -> j 不存在路径 { std::cout << "INFINITE" << "\t\t"; } else { std::cout << _arrDis[i][j] << "\t\t"; // 由于我们查询最短路径是从后往前插，因此我们把查询得到的节点 // 压入栈中，最后弹出以顺序输出结果。 std::stack<int> stackVertices; int k = j; do { k = _arrPath[i][k]; stackVertices.push( k ); } while ( k != i ); ////////////////////////////////////////////////////////////////////////// std::cout << stackVertices.top()+1; stackVertices.pop(); unsigned int nLength = stackVertices.size(); for ( unsigned int nIndex = 0; nIndex < nLength; ++nIndex ) { std::cout << " -> " << stackVertices.top()+1; stackVertices.pop(); } std::cout << " -> " << j+1 << std::endl; } } } } } int main( void ) { Graph myGraph; readGraphData( &myGraph ); ////////////////////////////////////////////////////////////////////////// int arrDis[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; int arrPath[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; // 先初始化arrDis for ( int i = 0; i < myGraph.nVertexCount; ++i ) { for ( int j = 0; j < myGraph.nVertexCount; ++j ) { arrDis[i][j] = myGraph.arrArcs[i][j]; } } floyd( arrDis, arrPath, myGraph.nVertexCount ); ////////////////////////////////////////////////////////////////////////// printResult( arrDis, arrPath, myGraph.nVertexCount ); ////////////////////////////////////////////////////////////////////////// system( "pause" ); return 0; }