dijkstra

//====================================
//              DIJKSTRA
//====================================

VertexT minimum(set<VertexT> T, vector<CostT> D){
    std::set<VertexT>::iterator it = T.begin();
    double min_val = D[(*it)];
    VertexT min_vert = (*it);

    for (auto v : T){
        if (D[v] < min_val){
            min_val = D[v];
            min_vert = v;
        }
    }

    return min_vert;
}


void Dijkstra(const DistanceGraph& g, GraphVisualizer& v, VertexT start,
    std::vector<CostT>& D) {

    size_t vertexCount = g.numVertices();
    D.resize(vertexCount);   //cost vector
    D[start] = 0;   //optimal distance (start -> start) = 0

    //R is set of vertices
    set<VertexT> R;
    for (size_t i = 0; i < vertexCount; i++){
        if (i != start){
            R.insert(i);
        }
    }

    //initialise D by iterating over all vertices except start
    for (auto v : R){
        D[v] = g.cost(start,v);
    }

    //main loop
    VertexT v1;
    while (!(R.empty())){
        v1 = minimum(R,D);  //finds vertex with minimal distance from v
        R.erase(v1);

        for (auto v : R){
            if (D[v] > D[v1] + g.cost(v1,v))
                D[v] = D[v1] + g.cost(v1,v);
        }
    }
}