I am creating a C++ file for Dijkstra’s Algorithm that supposes to read the dataset text file and use the data inside it to obtain the results for the file.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <fstream>
#include <sstream>
#include <iomanip>
// Star structure
struct nodeStar
{
std::string starName; // star name
int x, y, z; // location coordinates of star
int starWeight, starProfit; // weight and profit of star
std::vector<int> starConnections; // indices of connected stars
};
// Edge (path) structure
struct edgeStar
{
int distDeparture;
int distArrival;
int distWeight;
};
class starGraph
{
private:
std::vector<nodeStar> starnode;
std::vector<std::vector<edgeStar>> adjacencyList;
public:
// Load star data from the dataset
void loadStarDataset(const std::string &filename)
{
std::ifstream infile(filename);
if (!infile.is_open())
{
std::cerr << "Input file inaccessible, please try again." << std::endl;
return;
}
std::string line;
getline(infile, line); // Skip header
// Read star data line by line
while (getline(infile, line))
{
std::istringstream iss(line);
nodeStar star;
std::string temp;
// Read attributes about said star data
iss >> temp >> star.starName >> star.x >> star.y >> star.z >> star.starWeight >> star.starProfit;
starnode.push_back(star);
}
infile.close();
}
// Load connections between stars from the dataset
void loadStarConnections(const std::string &filename)
{
std::ifstream infile(filename);
if (!infile.is_open())
{
std::cerr << "Input file inaccessible, please try again." << std::endl;
return;
}
std::string line;
getline(infile, line); // Skip header
while (getline(infile, line)) // Read line by line
{
std::istringstream iss(line);
std::string name;
int x, y, z, weight, profit;
std::string temp;
// Read attributes about said star data
iss >> temp >> name >> x >> y >> z >> weight >> profit;
// find the star index by name
int starIndex = -1;
for (size_t i = 0; i < starnode.size(); ++i)
{
if (starnode[i].starName == name)
{
starIndex = i;
break;
}
}
if (starIndex == -1)
continue; // if star not found, skip to next line
// Read connections
std::vector<int> starConnections;
while (iss >> temp >> temp)
{
int connIndex;
for (size_t i = 0; i < starnode.size(); ++i)
{
if (starnode[i].starName == temp)
{
connIndex = i;
break;
}
}
if (connIndex == -1)
{
std::cerr << "Error: Star not found." << std::endl;
return;
}
starConnections.push_back(connIndex);
}
starnode[starIndex].starConnections = starConnections;
}
infile.close();
// Adjacency List with edges
adjacencyList.resize(starnode.size());
for (size_t i = 0; i < starnode.size(); i++)
{
for (int conn : starnode[i].starConnections)
{
int dist = std::abs(starnode[i].x - starnode[conn].x) + std::abs(starnode[i].y - starnode[conn].y) + std::abs(starnode[i].z - starnode[conn].z);
adjacencyList[i].push_back({(int)i, conn, dist});
}
}
}
// Dijkstra's algorithm
void dijkstraAlgo(int start)
{
// Initialize distances and previous node vectors
std::vector<int> dist(starnode.size(), std::numeric_limits<int>::max());
std::vector<int> prev(starnode.size(), -1);
dist[start] = 0;
// Priority queue to select the next node with the shortest known distance
using pii = std::pair<int, int>;
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
pq.push({0, start});
// Main loop of Dijkstra's algorithm
while (!pq.empty())
{
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// Skip if this distance is not the current shortest known distance
if (d > dist[u])
continue;
// Update distances for all adjacent nodes
for (const auto &edge : adjacencyList[u])
{
int v = edge.distArrival;
int weight = edge.distWeight;
if (d + weight < dist[v])
{
dist[v] = d + weight;
prev[v] = u; // Update the previous node
pq.push({dist[v], v}); // Add the updated node to the priority queue
}
}
}
printShortestPaths(start, dist, prev);
displayShortestDistances(start, dist);
}
void printShortestPaths(int start, const std::vector<int> &dist, const std::vector<int> &prev)
{
std::ofstream outfile("shortest_paths.txt");
if (!outfile.is_open())
{
std::cerr << "Error: Unable to open output file." << std::endl;
return;
}
for (size_t i = 0; i < starnode.size(); ++i)
{
if (i != start && dist[i] != std::numeric_limits<int>::max())
{
outfile << "Shortest path from " << starnode[start].starName << " to " << starnode[i].starName << " is " << dist[i] << " units long." << std::endl;
outfile << "Path: ";
printPath(i, prev, outfile);
outfile << std::endl;
}
}
outfile.close();
}
void displayShortestDistances(int start, const std::vector<int> &dist)
{
std::cout << std::setw(10) << "Star" << std::setw(20) << "Shortest Distance" << std::endl;
for (size_t i = 0; i < starnode.size(); ++i)
{
if (i != start && dist[i] != std::numeric_limits<int>::max())
{
std::cout << std::setw(10) << starnode[i].starName << std::setw(20) << dist[i] << std::endl;
}
}
}
void printPath(int current, const std::vector<int> &prev, std::ofstream &outfile)
{
if (current == -1)
return;
printPath(prev[current], prev, outfile);
outfile << starnode[current].starName << " ";
}
};
int main()
{
starGraph graph;
graph.loadStarDataset("star_dataset.txt");
graph.loadStarConnections("star_dataset_connections.txt");
int start = 0; // Assuming "Star 1" is the starting point, you can change it as needed.
graph.dijkstraAlgo(start);
std::cout << "Shortest paths computed and saved to shortest_paths.txt" << std::endl;
return 0;
}
Links for the dataset files:
https://1drv.ms/t/s!AltuclBCvxkj7GQHFzogure_RkGA?e=aS5Nmq
https://1drv.ms/t/s!AltuclBCvxkj7GMtr6ZOF2WMETS3?e=4bHh3d
Output shown here:
Shortest path from 1 to 2 is 4931 units long.
Path: 1 14 3 2
Shortest path from 1 to 3 is 1992 units long.
Path: 1 14 3
Shortest path from 1 to 4 is 4504 units long.
Path: 1 14 11 4
Shortest path from 1 to 6 is 6420 units long.
Path: 1 7 6
Shortest path from 1 to 7 is 2522 units long.
Path: 1 7
Shortest path from 1 to 8 is 4372 units long.
Path: 1 12 8
Shortest path from 1 to 9 is 4784 units long.
Path: 1 14 11 9
Shortest path from 1 to 10 is 4419 units long.
Path: 1 7 20 10
Shortest path from 1 to 11 is 3517 units long.
Path: 1 14 11
Shortest path from 1 to 12 is 2328 units long.
Path: 1 12
Shortest path from 1 to 13 is 3261 units long.
Path: 1 14 3 13
Shortest path from 1 to 14 is 978 units long.
Path: 1 14
Shortest path from 1 to 15 is 4229 units long.
Path: 1 14 3 13 15
Shortest path from 1 to 18 is 5389 units long.
Path: 1 7 20 10 18
Shortest path from 1 to 19 is 5961 units long.
Path: 1 12 8 19
Shortest path from 1 to 20 is 3444 units long.
Path: 1 7 20
Despite the output was working as expected, I felt like the answer is wrong. How do I fix it? Thanks.