3
\$\begingroup\$

I have a code that does applies Dijkstra's algorithm for an adjacency list.

The data are taken from a file. In the file, the first line contains the number of vertices and edges, and the remaining lines contain three elements each (the first 2 are the numbers of the vertices and 3rd are the weight of the edges).

The output is written to another file. The main problem is long reading (adding to the list) of elements - 8 seconds versus 2 according to the rules of the correct test. In a file for reading, there are 400,000 such lines. How can I speed up the reading?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;

class Graph
{
    int V;  
    list< pair<int, int> >* adj;
public:
    Graph(int V);  
    void addEdge(int u, int v, int w);
    void shortestPath(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair>[V];
}

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}


void Graph::shortestPath(int src)
{
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    vector<int> dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    ofstream file1("C:\\Tests\\123.txt");
    for (int i = 0; i < V; ++i)
        cout << dist[i] << " ";
    file1.close();
}

int main()
{
    ifstream file("C:\\Tests\\21");
    int number_of_veretexes, edges;
    file >> number_of_veretexes >> edges;
    Graph g(number_of_veretexes);
    int _first_, _second_, _third_;
    for (int i = 0; i < edges; i++) {
        file >> _first_ >> _second_ >> _third_;
        g.addEdge( _first_ - 1, _second_ - 1, _third_);
    }
    g.shortestPath(0);
    file.close();
}
\$\endgroup\$
5
  • \$\begingroup\$ Without looking at the details, your vector is probably resized and thereby reallocated many many times while it grows. If you know the total count upfront, resize the vector once right away. \$\endgroup\$
    – Aganju
    Mar 30, 2021 at 17:04
  • \$\begingroup\$ according to the rules of the correct test - What test? Is this for a coding challenge? If so, can you link us? \$\endgroup\$
    – Reinderien
    Mar 30, 2021 at 17:36
  • \$\begingroup\$ @Reinderien This is batch file.We run this bath file with exe file of this programm as first argument.This batch file check data and time. \$\endgroup\$ Mar 30, 2021 at 17:41
  • \$\begingroup\$ This is not quite Dijkstra's Algorithm though close. There is small difference in setting the minimum distance and thus probably do more work than required. This line dist[v] = dist[u] + weight; in Dijkstra's is done at the point where you pop the value (as now you have the shortest route to the node. If the value has already been set you then don't need to iterate over its adjacency list (potentially saving you work). Not sure if that will reduce the time by 400% that seems like a large gap. \$\endgroup\$ Mar 31, 2021 at 0:26
  • \$\begingroup\$ As it turned out, the problem was in the wrongly selected IDE, after installing the Code Blocks everything just started to fly.The code used to compile on Visual Studio \$\endgroup\$ Mar 31, 2021 at 14:41

3 Answers 3

3
\$\begingroup\$

Avoid using namespace std

Avoid using namespace std, it is considered bad practice. It saves only a little bit of typing, but you can run into issues if names of local classes and variables clash with those defined in the standard library.

Use INT_MAX instead of INF

Don't #define INF to some arbitrary value, just set it to exactly the largest possible value an int can have. This is already defined as INT_MAX in <climits>.

Create a struct Edge

Using a std::pair<int, int> is convenient, especially since you can sort them, but it has some drawbacks. It is unclear from just looking at the definition of this type whether the first element is the node number and the second the weight, or the other way around. You actually use both conventions in your code: the adjacency list has the vertex number first, whereas the priority queue has the vertex number second. Create a proper struct to remove the ambiguity and increase type safety. Also, since an edge is a property of a graph, define struct Edge inside class Graph, like so:

class Graph {
    struct Edge {
        int vertex;
        int weight;
    };

    std::list<Edge>* adj;
    ...
};

Instead of calling adj[u].push_back(std::make_pair(v, w)), you should now write:

adj[u].push_back({v, w});

For the priority queue, you also want to create a separate struct for the elements. Since only Graph::shortestPath() uses this, you can define this inside that function. To make it sortable, define an operator<() in this struct, like so:

void Graph::shortestPath(int src) {
    struct VertexDistance {
         int vertex;
         int distance;
         bool operator<(const VertexDistance &other) {
             if (distance != other.distance)
                 return distance > other.distance;
             else
                 return vertex > other.vertex;
         }
    };

    std::priority_queue<VertexDistance> pq;
    ...
}

Avoid manual memory allocation

It is a bit strange to see you use STL containers like std::list and std::vector and std::priority_queue, but then use new to allocate the array adj. Why not use a std::vector for that too? For example, like so:

std::vector<std::list<Edge>> adj;

This avoids the need for new, and fixes the memory leak you have because you never call delete. It also allows you to remove the member variable V, since the vector already keeps track of its size.

You can make it a bit easier to read by creating an alias for the list of edges:

using AdjacencyList = std::list<Edge>;
std::vector<AdjacencyList> adj;

Use std::vector instead of std::list

std::vector and std::list can both store a list of elements, but they have different tradeoffs in performance, memory requirements, and other aspects. In your code, you only ever add elements to the back of an adjacency list, you never insert or remove elements from the middle. In that case, a std::vector is a much more efficient data structure, so I would just write:

using AdjacencyList = std::vector<Edge>;
std::vector<AdjacencyList> adj;

Use range-based for loops

Unless you cannot use any features from C++11 or later, I strongly recommend you start using range-based for-loops. They save typing, make the code more readable and reduce the possibility of errors. For example, when iterating over an adjacency list in Graph::shortestPath(), you can write:

for (auto &edge: adj[u]) {
     int v = edge.vertex;
     int weight = edge.weight;
     ...
}

The same goes for printing the contents of dist:

for (auto &distance: dist)
    file << distance << " ";

Check for errors when reading and writing files

A lot of things can go wrong when reading from and writing to files: the files might not exist, be corrupted, you might not have permissions to read and/or write, the disk might get full halfway writing a file, and so on. You should therefore ensure that you have completely read and written files without errors.

You don't have to check every I/O operation; the file objects will remember if an error condition has occured in the past. So the simplest way to get proper error checking is to do this after reading or writing the whole file. This can be done by checking the I/O state bits. In your case, just checking that good() returns true should be sufficient, like so for the input file:

int main() {
    ifstream file("...");
    ...
    if (!file.good()) {
        std::cerr << "An error occured while reading the input!\n";
        return 1;
    }

    g.shortestPath(0);
}

And like so for the output file:

void Graph::shortestPath(int src) {
    ...
    ofstream file("...");
    ...
    file.close();
    if (!file.good()) {
        std::cerr << "An error occured while writing the output!\n";
        // TODO: ensure the error propagates to main, or call exit(1)
    }
}

It is imporant to call close() first here, since the act of closing the stream will ensure its output buffer is completely flushed.

When you detect an error, it is important that you don't continue using any bad data you might have gotten, that you print a helpful error message to std::cerr, and that if your program returns a non-zero exit code. The latter is important in case your program is called from a script for example, so the script won't continue with bogus data.

Move file output out of Graph::shortestPath()

Following the principle of separation of concerns, you should remove the file output functionality from shortestPath(). Instead, make that function return the shortest path, and let the caller write it to disk. This can simply be done like so:

std::vector<int> Graph::shortestPath(int src)
{
    ...
    while (...) {
        ...
    }

    return dist;
}

int main()
{
    ...
    auto path = g.shortestPath(0);
    std::ofstream file1(...);

    for (auto &distance: path)
        file1 << distance < " ";

    file1.close();

    if (!file1.good()) {
        std::cerr << "An error occured while writing the output!\n";
        return 1;
    }
}

You might also consider moving the file input and output into separate functions, so that main() is simplified to something that looks like this:

int main() {
    auto graph = readGraph("C:\\Tests\\21");
    auto path = graph.shortestPath(0);
    writePath(path, "C:\\Tests\123.txt");
}
\$\endgroup\$
2
\$\begingroup\$

Everything @G. Sliepen said.

Small change in the algorithm.

Your original algorithm was Dijkstra like. But the difference meant that you potentially expanded a lot more nodes than you needed to. This would mean you added more items to the priority queue which takes time and space and may be enefecient.

Below is more traditional implementation of Dijkstra's.

vector<int> Graph::shortestPath(int src)
{
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    vector<int> dist(V, INT_MAX);

    pq.push(make_pair(0, src));

    while (!pq.empty())
    {
        int u    = pq.top().second;
        int d2u  = pq.top().first;
        pq.pop();

        // You were missing this first test.
        // And the following update to `dist[u]`
        if (dist[u] != INT_MAX) {
            // Already done this node we can ignore.
            continue;
        }

        // First time we made it to this node.
        // Record the distance (it must be the shortest as pq is priority based).
        dist[u] = d2u;
        
        // Loop over all edges from this node.
        for (auto const& item: adj[u])
        {
            int v      = item.first;
            int weight = item.second;

            // Optimization. Don't need this as pq is priority based.
            //               May or may not help.
            if (dist[v] != INT_MAX)
            {
                pq.push({d2u + weight, v});
            }
        }
    }
    return dist;
}
\$\endgroup\$
0
\$\begingroup\$

I suspect that push_back is much more costly than push. (Or maybe vice versa?) (I assume it involves an array (vector) and it is cheaper to tack onto the end than to shift all the contents to make room at the start.)

So, instead of doing push_back, do push. Then, when finished, reverse the contents of the vector.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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