I have to implement Floyd-Warshall algorithm in the road-graph plugin in QGIS. I have written the following code in qgsgraphanalyzer.cpp and qgsgraphanalyzer.h, and checked my output with the output of Djikstra's algorithm which gives the same result but still my algo dosen't work?
void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector* resultTree, QVector* resultCost ){ QVector< double > * result = NULL;if ( resultCost != NULL ){ result = resultCost;}else{ result = new QVector();}result->clear();result->insert( result->begin(), source->vertexCount(), std::numeric_limits::infinity() );( *result )[ startPointIdx ] = 0.0;if ( resultTree != NULL ){ resultTree->clear(); resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );}// QMultiMap< cost, vertexIdx > not_begin// I use it and not create any struct or class.QMultiMap< double, int > not_begin;QMultiMap< double, int >::iterator it;not_begin.insert( 0.0, startPointIdx );while ( !not_begin.empty() ){ it = not_begin.begin(); double curCost = it.key(); int curVertex = it.value(); not_begin.erase( it ); // edge index list QgsGraphArcIdList l = source->vertex( curVertex ).outArc(); QgsGraphArcIdList::iterator arcIt; for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt ) { const QgsGraphArc arc = source->arc( *arcIt ); double cost = arc.property( criterionNum ).toDouble() + curCost; if ( cost < ( *result )[ arc.inVertex()] ) { ( *result )[ arc.inVertex()] = cost; if ( resultTree != NULL ) { ( *resultTree )[ arc.inVertex()] = *arcIt; } not_begin.insert( cost, arc.inVertex() ); } }}if ( resultCost == NULL ) { delete result; }}void QgsGraphAnalyzer::floydwarshall( const QgsGraph* source, int startPointIdx, int criterionNum, QVector* resultTree ){int vertexCount = source->vertexCount();vector adj_matrix(vertexCount, vector(vertexCount, INF));vector prev(vertexCount, vector(vertexCount, -1));for (int i = 0; i < vertexCount; ++i){ QgsGraphArcIdList l = source->vertex( i ).outArc(); QgsGraphArcIdList::iterator arcIt; for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt ) { const QgsGraphArc arc = source->arc( *arcIt ); double cost = arc.property( criterionNum ).toDouble(); adj_matrix[arc.outVertex()][arc.inVertex()] = cost; }}for (int i = 0; i < vertexCount; ++i){ for (int j = 0; j < vertexCount; ++j) { if(adj_matrix[j] != INF) prev[j] = i; else prev[j] = -1; }}for (int k = 0; k < vertexCount; ++k){ for (int i = 0; i < vertexCount; ++i) { for (int j = 0; j < vertexCount; ++j) { if(adj_matrix[k] + adj_matrix[k][j] < adj_matrix[j]) { adj_matrix[j] = adj_matrix[k] + adj_matrix[k][j]; prev[j] = prev[k][j]; } } }}if ( resultTree != NULL ){ resultTree->clear(); resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );}for (int i = 0; i < vertexCount; ++i){ if ( resultTree != NULL && prev[startPointIdx]!=-1) { QgsGraphArcIdList l1 = source->vertex( i ).inArc(); QgsGraphArcIdList l2 = source->vertex( prev[startPointIdx] ).outArc(); QgsGraphArcIdList::iterator arcIt1; QgsGraphArcIdList::iterator arcIt2; for (arcIt1 = l1.begin(); arcIt1 != l1.end(); ++arcIt1 ) { for (arcIt2 = l2.begin(); arcIt2 != l2.end(); ++arcIt2 ) { if (*arcIt1 == *arcIt2 && *arcIt1!=-1 ) { ( *resultTree ) = *arcIt1; } } } } }}QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum ){QgsGraph *treeResult = new QgsGraph();QVector tree;QgsGraphAnalyzer::floydwarshall( source, startVertexIdx, criterionNum, &tree );// sourceVertexIdx2resultVertexIdxQVector source2result( tree.size(), -1 );// Add reachable vertices to the resultsource2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );int i = 0;for ( i = 0; i < source->vertexCount(); ++i ){ if ( tree[ i ] != -1 ) { source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() ); }}// Add arcs to resultfor ( i = 0; i < source->vertexCount(); ++i ){ if ( tree[ i ] != -1 ) { const QgsGraphArc& arc = source->arc( tree ); treeResult->addArc( source2result[ arc.outVertex()], source2result[ arc.inVertex()], arc.properties() ); } } return treeResult;}
أكثر...
void QgsGraphAnalyzer::dijkstra( const QgsGraph* source, int startPointIdx, int criterionNum, QVector* resultTree, QVector* resultCost ){ QVector< double > * result = NULL;if ( resultCost != NULL ){ result = resultCost;}else{ result = new QVector();}result->clear();result->insert( result->begin(), source->vertexCount(), std::numeric_limits::infinity() );( *result )[ startPointIdx ] = 0.0;if ( resultTree != NULL ){ resultTree->clear(); resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );}// QMultiMap< cost, vertexIdx > not_begin// I use it and not create any struct or class.QMultiMap< double, int > not_begin;QMultiMap< double, int >::iterator it;not_begin.insert( 0.0, startPointIdx );while ( !not_begin.empty() ){ it = not_begin.begin(); double curCost = it.key(); int curVertex = it.value(); not_begin.erase( it ); // edge index list QgsGraphArcIdList l = source->vertex( curVertex ).outArc(); QgsGraphArcIdList::iterator arcIt; for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt ) { const QgsGraphArc arc = source->arc( *arcIt ); double cost = arc.property( criterionNum ).toDouble() + curCost; if ( cost < ( *result )[ arc.inVertex()] ) { ( *result )[ arc.inVertex()] = cost; if ( resultTree != NULL ) { ( *resultTree )[ arc.inVertex()] = *arcIt; } not_begin.insert( cost, arc.inVertex() ); } }}if ( resultCost == NULL ) { delete result; }}void QgsGraphAnalyzer::floydwarshall( const QgsGraph* source, int startPointIdx, int criterionNum, QVector* resultTree ){int vertexCount = source->vertexCount();vector adj_matrix(vertexCount, vector(vertexCount, INF));vector prev(vertexCount, vector(vertexCount, -1));for (int i = 0; i < vertexCount; ++i){ QgsGraphArcIdList l = source->vertex( i ).outArc(); QgsGraphArcIdList::iterator arcIt; for ( arcIt = l.begin(); arcIt != l.end(); ++arcIt ) { const QgsGraphArc arc = source->arc( *arcIt ); double cost = arc.property( criterionNum ).toDouble(); adj_matrix[arc.outVertex()][arc.inVertex()] = cost; }}for (int i = 0; i < vertexCount; ++i){ for (int j = 0; j < vertexCount; ++j) { if(adj_matrix[j] != INF) prev[j] = i; else prev[j] = -1; }}for (int k = 0; k < vertexCount; ++k){ for (int i = 0; i < vertexCount; ++i) { for (int j = 0; j < vertexCount; ++j) { if(adj_matrix[k] + adj_matrix[k][j] < adj_matrix[j]) { adj_matrix[j] = adj_matrix[k] + adj_matrix[k][j]; prev[j] = prev[k][j]; } } }}if ( resultTree != NULL ){ resultTree->clear(); resultTree->insert( resultTree->begin(), source->vertexCount(), -1 );}for (int i = 0; i < vertexCount; ++i){ if ( resultTree != NULL && prev[startPointIdx]!=-1) { QgsGraphArcIdList l1 = source->vertex( i ).inArc(); QgsGraphArcIdList l2 = source->vertex( prev[startPointIdx] ).outArc(); QgsGraphArcIdList::iterator arcIt1; QgsGraphArcIdList::iterator arcIt2; for (arcIt1 = l1.begin(); arcIt1 != l1.end(); ++arcIt1 ) { for (arcIt2 = l2.begin(); arcIt2 != l2.end(); ++arcIt2 ) { if (*arcIt1 == *arcIt2 && *arcIt1!=-1 ) { ( *resultTree ) = *arcIt1; } } } } }}QgsGraph* QgsGraphAnalyzer::shortestTree( const QgsGraph* source, int startVertexIdx, int criterionNum ){QgsGraph *treeResult = new QgsGraph();QVector tree;QgsGraphAnalyzer::floydwarshall( source, startVertexIdx, criterionNum, &tree );// sourceVertexIdx2resultVertexIdxQVector source2result( tree.size(), -1 );// Add reachable vertices to the resultsource2result[ startVertexIdx ] = treeResult->addVertex( source->vertex( startVertexIdx ).point() );int i = 0;for ( i = 0; i < source->vertexCount(); ++i ){ if ( tree[ i ] != -1 ) { source2result[ i ] = treeResult->addVertex( source->vertex( i ).point() ); }}// Add arcs to resultfor ( i = 0; i < source->vertexCount(); ++i ){ if ( tree[ i ] != -1 ) { const QgsGraphArc& arc = source->arc( tree ); treeResult->addArc( source2result[ arc.outVertex()], source2result[ arc.inVertex()], arc.properties() ); } } return treeResult;}
أكثر...