|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#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
Nodestructure 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.
- The
- 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
distancesto 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
mainfunction 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.
- The
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.