Simulation of Routing Algorithms Gaming Project in C++

Projects Inventory

3 months ago

#include <iostream>
#include <vector>
#include <climits>
#include <queue>

const int INF = INT_MAX;

// Class to represent a graph
class Graph {
public:
    Graph(int vertices) : adj(vertices, std::vector<std::pair<int, int>>()) {}

    // Add an edge to the graph
    void addEdge(int u, int v, int w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w); // For undirected graph
    }

    // Function to perform Dijkstra's algorithm from a source vertex
    std::vector<int> dijkstra(int src) {
        int V = adj.size();
        std::vector<int> dist(V, INF);
        std::vector<bool> visited(V, false);
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;

        dist[src] = 0;
        pq.emplace(0, src);

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

            if (visited[u]) continue;
            visited[u] = true;

            for (const auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.emplace(dist[v], v);
                }
            }
        }

        return dist;
    }

private:
    std::vector<std::vector<std::pair<int, int>>> adj;
};

int main() {
    int V = 5; // Number of vertices
    Graph g(V);

    // Adding edges (u, v, weight)
    g.addEdge(0, 1, 10);
    g.addEdge(0, 4, 3);
    g.addEdge(1, 2, 2);
    g.addEdge(1, 4, 4);
    g.addEdge(2, 3, 9);
    g.addEdge(3, 4, 7);

    int src = 0; // Starting vertex
    std::vector<int> distances = g.dijkstra(src);

    std::cout << "Vertex\tDistance from Source\n";
    for (int i = 0; i < distances.size(); ++i) {
        std::cout << i << "\t\t" << (distances[i] == INF ? "INF" : std::to_string(distances[i])) << "\n";
    }

    return 0;
}

#include <iostream>

#include <vector>

#include <climits>

#include <queue>

const int INF = INT_MAX;

// Class to represent a graph

class Graph {

public:

Graph(int vertices) : adj(vertices, std::vector<std::pair<int, int>>()) {}

// Add an edge to the graph

void addEdge(int u, int v, int w) {

adj[u].emplace_back(v, w);

adj[v].emplace_back(u, w); // For undirected graph

}

// Function to perform Dijkstra's algorithm from a source vertex

std::vector<int> dijkstra(int src) {

int V = adj.size();

std::vector<int> dist(V, INF);

std::vector<bool> visited(V, false);

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;

dist[src] = 0;

pq.emplace(0, src);

while (!pq.empty()) {

int u = pq.top().second;

pq.pop();

if (visited[u]) continue;

visited[u] = true;

for (const auto& edge : adj[u]) {

int v = edge.first;

int weight = edge.second;

if (!visited[v] && dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;

pq.emplace(dist[v], v);

}

return dist;

}

private:

std::vector<std::vector<std::pair<int, int>>> adj;

};

int main() {

int V = 5; // Number of vertices

Graph g(V);

// Adding edges (u, v, weight)

g.addEdge(0, 1, 10);

g.addEdge(0, 4, 3);

g.addEdge(1, 2, 2);

g.addEdge(1, 4, 4);

g.addEdge(2, 3, 9);

g.addEdge(3, 4, 7);

int src = 0; // Starting vertex

std::vector<int> distances = g.dijkstra(src);

std::cout << "Vertex\tDistance from Source\n";

for (int i = 0; i < distances.size(); ++i) {

std::cout << i << "\t\t" << (distances[i] == INF ? "INF" : std::to_string(distances[i])) << "\n";

}

return 0;

}

Explanation

Graph Class:
- Attributes:
  - adj: Adjacency list representation of the graph. Each vertex has a list of pairs representing adjacent vertices and edge weights.
- Methods:
  - addEdge(int u, int v, int w): Adds an undirected edge between vertices u and v with weight w.
  - dijkstra(int src): Computes the shortest paths from source vertex src
    
    Advertisement
    
    using Dijkstra’s algorithm.
Dijkstra’s Algorithm:
- Purpose: Finds the shortest path from the source vertex to all other vertices in the graph.
- Data Structures:
  - Priority Queue: Stores vertices to be processed, ordered by their current shortest distance.
  - Distance Vector: Maintains the shortest distance from the source to each vertex.
  - Visited Vector: Keeps track of vertices that have been processed.
- Algorithm:
  - Initialize distances to all vertices as infinity, except the source vertex.
  - Use a priority queue to explore vertices with the smallest known distance.
  - Update distances based on the weights of the edges and the shortest paths found.
Main Function:
- Graph Creation: Initializes a graph with a specified number of vertices and adds edges.
- Distance Calculation: Calls dijkstra to compute shortest paths from the source vertex.
- Result Display: Prints the shortest distance from the source vertex to each vertex.

Usage

Routing Simulation: Demonstrates how to use Dijkstra’s algorithm for routing and finding shortest paths in a graph.
Graph-Based Games: Useful for implementing pathfinding and routing features in graph-based or grid-based games.

Explanation

Usage

Related Posts: