43 ( *result )[ startPointIdx ] = 0.0;
56 not_begin.
insert( 0.0, startPointIdx );
58 while ( !not_begin.
empty() )
60 it = not_begin.
begin();
61 double curCost = it.
key();
62 int curVertex = it.
value();
63 not_begin.
erase( it );
68 for ( arcIt = l.
begin(); arcIt != l.
end(); ++arcIt )
73 if ( cost < ( *result )[ arc.
inVertex()] )
78 ( *resultTree )[ arc.
inVertex()] = *arcIt;
101 source2result[ startVertexIdx ] = treeResult->
addVertex( source->
vertex( startVertexIdx ).
point() );
105 if ( tree[ i ] != -1 )
114 if ( tree[ i ] != -1 )
const QgsGraphArc & arc(int idx) const
return edge at index
int inVertex() const
return index of incoming vertex
iterator erase(iterator pos)
QVariant property(int propertyIndex) const
return property value
QgsGraphArcIdList outArc() const
return outgoing edges
void insert(int i, const T &value)
QgsPoint point() const
return vertex point
int outVertex() const
return index of outgoing vertex
QVector< QVariant > properties() const
get array of properties
This class implement a graph edge.
int addArc(int outVertexIdx, int inVertexIdx, const QVector< QVariant > &properties)
add edge to a graph
int addVertex(const QgsPoint &pt)
add vertex to a grap
QMap< Key, T >::iterator insert(const Key &key, const T &value)
static QgsGraph * shortestTree(const QgsGraph *source, int startVertexIdx, int criterionNum)
return shortest path tree with root-node in startVertexIdx
Mathematics graph representation.
double toDouble(bool *ok) const
const QgsGraphVertex & vertex(int idx) const
return vertex at index
int vertexCount() const
return vertex count
static void dijkstra(const QgsGraph *source, int startVertexIdx, int criterionNum, QVector< int > *resultTree=nullptr, QVector< double > *resultCost=nullptr)
solve shortest path problem using dijkstra algorithm