2
\$\begingroup\$

If std::vector<vector<pair<int,int> > > v(n) represents the adjacency list of the graph with pair<int,int> is the {vertex,weight} pair, I tried to implement the algorithm the following way:

while(true)
        {
            long long yo = LLONG_MAX;
            int ind=-1;
            for(int i=0;i<n;++i)
            {
                if(ans[i]<yo && !v[i].empty())
                {
                    ind=i;
                    yo=ans[i];
                }
            }
            if(ind==-1)
                break;
            for(int i=0;i<v[ind].size();++i)
            {
                if(ans[v[ind][i].first] > ans[ind]+v[ind][i].second)
                    ans[v[ind][i].first] = ans[ind]+v[ind][i].second;
                v[ind].erase(v[ind].begin()+i);
            }
        }

Where ans[i] stores the shortest paths which is initialised as {LLONG_MAX,...0,...LLONG_MAX}, 0 being the source. Since this is the first time I tried implementing it, is there a better way to implement using the vectors/list in stl (in terms of time/space complexity maybe)?

\$\endgroup\$
1
\$\begingroup\$
for(int i=0;i<v[ind].size();++i) {
    ...
    v[ind].erase(v[ind].begin()+i);
}

It looks like a bug. For instance, when you erase the 0-th element all other elements get shifted, so the new element at position 0 will never be deleted. You can just iterator over the vector and clear it after the loop.

I don't see the point in removing the graph edges after the vertex is processed. I'd suggest to create a separate vector (used or visited) to keep track of processed vertices and leave the input graph unchanged.

If the graph is sparse, you can improve the time complexity from O(|V|^2) to O(|E| log |V|) or even O(|E| + |V| log |V|) using an appropriate data structure (like a heap).

I'd also suggest to create a separate class for an edge instead of using std::pair<int, int>. It's hard to confuse edge.weight with edge.destination_vertex. It's easy to confuse the first and the second elements of the pair (it's not easy to keep the meaning of the first and the second elements of the pair in one's head).

You can make the code more readable by naming your variables in a more meaningful way (for instance, what is yo? It's something like min_distance, isn't it?).

When you need to iterate over a container and you don't need elements' indices, you can use a range-based for loop. For instance, this:

for(int i=0;i<v[ind].size();++i)
{
    if(ans[v[ind][i].first] > ans[ind]+v[ind][i].second)
        ans[v[ind][i].first] = ans[ind]+v[ind][i].second;
    v[ind].erase(v[ind].begin()+i);
}

could be

for (auto edge: v[ind]) { // or const auto& edge for heavier objects
// do something with the edge
}

You can also improve the readability of your code by creating smaller functions with a meaningful name that do one focused thing (like finding the closest vertex and so on) and call them from the function that implements Dijkstra's algorithm itself. Here's how I'd do it:

// Instances of this struct represent graph edges
struct Edge {
    int weight;
    int destination_vertex;

    Edge(int _weight, int _destination_vertex): 
        weight(_weight), destination_vertex(_destination_vertex) {}
};

// Finds the closest unvisited vertex
int get_closest_unvisited_vertex(const vector<long long>& dist,
        const vector<bool>& visited) {
    int closest_vertex = -1;
    for (size_t v = 0; v < dist.size(); v++) {
        if (!visited[v] 
                && (closest_vertex == -1 || dist[v] < dist[closest_vertex])) {
            closest_vertex = v;
        }
    }
    return closest_vertex;
}

// Updates the distances to all neighbors of the given vertex
// The dist vector is passed by reference to avoid copying the data
void relax_vertex(int vertex, const vector<vector<Edge>>& graph,
        vector<long long>& dist) { 
    for (auto edge : graph[vertex]) {
        dist[edge.destination_vertex] = min(dist[edge.destination_vertex], 
                dist[vertex] + edge.weight);
    }
}

// Finds the distance from the source vertex to all other vertices in
// the graph
vector<long long> get_distance_from(const vector<vector<Edge>>& graph,
        int source) {
    vector<long long> dist(graph.size(), numeric_limits<long long>::max());
    dist[source] = 0;
    vector<bool> visited(graph.size());
    while (true) {
        int closest_vertex = get_closest_unvisited_vertex(dist, visited);
        if (closest_vertex == -1 
                || dist[closest_vertex] == numeric_limits<long long>::max()) {
            break;
        }
        visited[closest_vertex] = true;
        relax_vertex(closest_vertex, graph, dist);
    }
    return dist;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.