#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;
}
