Dijkstra’s Algorithm Gaming Project in C++

Projects Inventory

3 months ago

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // Represents infinity

// A structure to represent a node in the priority queue
struct Node {
    int vertex, distance;
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};

// Function to perform Dijkstra's algorithm
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> distances(n, INF);
    distances[start] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({start, 0});

    while (!pq.empty()) {
        int currentVertex = pq.top().vertex;
        int currentDistance = pq.top().distance;
        pq.pop();

        // Explore the neighbors
        for (const auto& neighbor : graph[currentVertex]) {
            int nextVertex = neighbor.first;
            int weight = neighbor.second;

            int newDistance = currentDistance + weight;

            // If a shorter path is found
            if (newDistance < distances[nextVertex]) {
                distances[nextVertex] = newDistance;
                pq.push({nextVertex, newDistance});
            }
        }
    }

    return distances;
}

int main() {
    int vertices = 6;
    vector<vector<pair<int, int>>> graph(vertices);

    // Adding edges to the graph (graph is represented as an adjacency list)
    graph[0].push_back({1, 7});
    graph[0].push_back({2, 9});
    graph[0].push_back({5, 14});
    graph[1].push_back({0, 7});
    graph[1].push_back({2, 10});
    graph[1].push_back({3, 15});
    graph[2].push_back({0, 9});
    graph[2].push_back({1, 10});
    graph[2].push_back({3, 11});
    graph[2].push_back({5, 2});
    graph[3].push_back({1, 15});
    graph[3].push_back({2, 11});
    graph[3].push_back({4, 6});
    graph[4].push_back({3, 6});
    graph[4].push_back({5, 9});
    graph[5].push_back({0, 14});
    graph[5].push_back({2, 2});
    graph[5].push_back({4, 9});

    int startVertex = 0;
    vector<int> distances = dijkstra(startVertex, graph);

    cout << "Shortest distances from vertex " << startVertex << ":\n";
    for (int i = 0; i < vertices; ++i) {
        if (distances[i] == INF) {
            cout << "Vertex " << i << ": INF (unreachable)" << endl;
        } else {
            cout << "Vertex " << i << ": " << distances[i] << endl;
        }
    }

    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // Represents infinity

// A structure to represent a node in the priority queue

struct Node {

int vertex, distance;

bool operator>(const Node& other) const {

return distance > other.distance;

}

};

// Function to perform Dijkstra's algorithm

vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {

int n = graph.size();

vector<int> distances(n, INF);

distances[start] = 0;

priority_queue<Node, vector<Node>, greater<Node>> pq;

pq.push({start, 0});

while (!pq.empty()) {

int currentVertex = pq.top().vertex;

int currentDistance = pq.top().distance;

pq.pop();

// Explore the neighbors

for (const auto& neighbor : graph[currentVertex]) {

int nextVertex = neighbor.first;

int weight = neighbor.second;

int newDistance = currentDistance + weight;

// If a shorter path is found

if (newDistance < distances[nextVertex]) {

distances[nextVertex] = newDistance;

pq.push({nextVertex, newDistance});

}

return distances;

}

int main() {

int vertices = 6;

vector<vector<pair<int, int>>> graph(vertices);

// Adding edges to the graph (graph is represented as an adjacency list)

graph[0].push_back({1, 7});

graph[0].push_back({2, 9});

graph[0].push_back({5, 14});

graph[1].push_back({0, 7});

graph[1].push_back({2, 10});

graph[1].push_back({3, 15});

graph[2].push_back({0, 9});

graph[2].push_back({1, 10});

graph[2].push_back({3, 11});

graph[2].push_back({5, 2});

graph[3].push_back({1, 15});

graph[3].push_back({2, 11});

graph[3].push_back({4, 6});

graph[4].push_back({3, 6});

graph[4].push_back({5, 9});

graph[5].push_back({0, 14});

graph[5].push_back({2, 2});

graph[5].push_back({4, 9});

int startVertex = 0;

vector<int> distances = dijkstra(startVertex, graph);

cout << "Shortest distances from vertex " << startVertex << ":\n";

for (int i = 0; i < vertices; ++i) {

if (distances[i] == INF) {

cout << "Vertex " << i << ": INF (unreachable)" << endl;

} else {

cout << "Vertex " << i << ": " << distances[i] << endl;

}

return 0;

}

Explanation:

Graph Representation:
- The graph is represented as an adjacency list using a vector of vectors. Each inner vector contains pairs representing a connected vertex and the weight of the edge to that vertex.
Node Structure:
- The Node structure is used to store the current vertex and the distance from the source vertex. It also includes a custom comparison operator to allow the priority queue to prioritize nodes with the smallest distance.
Dijkstra’s Algorithm (dijkstra):
- The function takes the starting vertex and the graph as input and returns a vector of the shortest distances from the start vertex to all other vertices.
- It initializes a vector distances to store the shortest known distance to each vertex, setting all distances to infinity (INF) initially except the start vertex, which is set to 0.
- A priority queue is used to always expand the least costly node. The algorithm then iterates through each node’s neighbors, updating their distances if a shorter path is found.
Main Function (main):
- The main function creates a sample graph with 6 vertices and various weighted edges.
- It runs Dijkstra’s algorithm from the starting vertex (vertex 0) and prints out the shortest distances to all other vertices.

Possible Enhancements:

Path Reconstruction: Modify the algorithm to also keep track of the actual path taken, not just the distance.
Graph Input: Implement functionality to dynamically input graphs rather than hardcoding them.
Multiple Source Nodes: Extend the algorithm to handle multiple source nodes or to find shortest paths between all pairs of nodes.
Optimization: Explore optimizations such as using Fibonacci heaps for the priority queue to improve efficiency for larger graphs.

Explanation:

Possible Enhancements:

Related Posts: