0

我已经使用 C++ 中的邻接矩阵实现了 Floyd Warshall 算法，如下所示，但是我使用了邻接矩阵表示，这使得循环 (i,j,k) 索引非常方便。有没有办法在邻接表表示中实现这一点？我看到即使http://mcs.uwsuper.edu/sb/425/Prog/FloydWarshall.java这个站点在应用算法之前将邻接列表转换为矩阵。

int rowSize = numberOfGraphVertices,  colSize = numberOfGraphVertices ;
    std::vector<int> shortestPathMatrix(rowSize * colSize, 10000000);

    for (int i = 0; i < rowSize; ++i) shortestPathMatrix[i + i * colSize] = 0 ;
    cout << "Done" << endl ; 
    int numEdges = 0;
    while(getline(infile, graphString)) // To get you all the lines.
    {

         pch = strtok_s(const_cast<char *> (graphString.c_str())," ", &p2);
         int rowNumber = atoi(pch);
        //graphListVector[node1] = 
         pch = strtok_s(NULL, " ", &p2);
         int colNumber = atoi(pch);
         pch = strtok_s(NULL, " ", &p2);
         int edgeWeight = atoi(pch);
         shortestPathMatrix[(rowNumber-1)*colSize + (colNumber-1)] = edgeWeight;
         ++numEdges;
    }
    cout<< "numberOfVertices"<<numberOfGraphVertices<<"NumberOfEdges"<< numEdges <<endl;
    t = clock();
    //for (int i = 0 ; i < 1002 ; ++i) cout << "Value" << i <<" " << shortestPathMatrix[i] << endl; 
    for (int k = 0 ; k < rowSize ; ++k){
        for (int i = 0 ; i < rowSize ; ++i){
            for (int j = 0; j < rowSize ; ++j){
                if ( shortestPathMatrix[j*colSize + i] + shortestPathMatrix[i*colSize + k] < shortestPathMatrix[j*colSize + k])
                    shortestPathMatrix[j*colSize + k] = shortestPathMatrix[j*colSize + i] + shortestPathMatrix[i*colSize + k];
            }
        }
    }
    for (int i = 0; i < rowSize; ++i) {
        if (shortestPathMatrix[i + i * colSize] < 0) cout << "Negative cycle found" << endl;
        break;
    }
     std::vector<int>::iterator minShortestPathIndex = std::min_element (shortestPathMatrix.begin(), shortestPathMatrix.end());
4

0 回答 0