dijkstra_sssp< graph > Class Template Reference

Public Member Functions
	dijkstra_sssp (graph &g, vertex_t source)
long long	dist_to (vertex_t dest)
	dijkstra_sssp (graph &g, vertex &source)
int	dist_to (vertex &dest)

Constructor & Destructor Documentation

template<typename graph >

dijkstra_sssp< graph >::dijkstra_sssp	(	graph &	g,
		vertex_t	source
	)

                                                             : G(g), src(source) {

    const int inf = 1000000000; // A constexpr - evaled at compile-time.
    
    // The set E stores our best estimate for the shortest path to each vertex.
    // The one with the least estimate is transferred to the set S and all the edges leaving it are relaxed
    set<pair<int, vertex_t>> E; // ordered by distance

    for(auto it = G.vbegin(); it != G.vend(); it++) {
        dist[*it] = inf;
    }   

    dist[source] = 0;
    E.insert(make_pair(dist[source], source));
    
    while(!E.empty()) {
        pair<int, vertex_t> least = *E.begin();
        E.erase(*E.begin());
        
        int path_len = least.first;
        vertex_t u = least.second;
        
        // TODO : segregate relax procedure
        
        // relax all the outbound edges
        for(auto it = G.aebegin(u); it != G.aeend(u); it++) {
        
            vertex_t v = it->to();
            int wt = it->weight();
            
            // Improve estimate
            if(dist[u] + wt < dist[v]) {
                typename set<pair<int, vertex_t>>::iterator it;
                if((it = E.find(make_pair(dist[v], v))) != E.end())
                    E.erase(it);
                dist[v] = dist[u] + wt;
                E.insert(make_pair(dist[v], v));
            }
        }
    }   
    
}

template<typename graph>

dijkstra_sssp< graph >::dijkstra_sssp	(	graph &	g,
		vertex &	source
	)

Member Function Documentation

template<typename graph>

int dijkstra_sssp< graph >::dist_to

(

vertex &

dest

)

                                       {
    return dist[dest];
}

template<typename graph >

long long dijkstra_sssp< graph >::dist_to

(

vertex_t

dest

)

                                                     {
    if(dest == src)
        return 0;
    else if(dist[dest] == 0 or dist[dest] > 100000000)
        return -1;
    return dist[dest];
}

---

The documentation for this class was generated from the following files:

• alglib/graph/dijkstra.cpp
• alglib/graph/legacy/shortest_path.cpp