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");
}
Dijkstra's Algorithmthough close. There is small difference in setting the minimum distance and thus probably do more work than required. This linedist[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\$