#include <iostream>
#include <vector>
#include <limits>
#include <set>
const int INF = std::numeric_limits<int>::max();
void dijkstra(const std::vector<std::vector<int>>& graph, int src) {
int V = [Link]();
std::vector<int> dist(V, INF); // Distance from source to each vertex
std::vector<bool> visited(V, false); // Visited vertices
dist[src] = 0;
// Use a set to store vertices that are being processed
std::set<std::pair<int, int>> setds; // (distance, vertex)
[Link](std::make_pair(0, src));
while (![Link]()) {
// Get the vertex with the minimum distance
std::pair<int, int> tmp = *([Link]());
[Link]([Link]());
int u = [Link];
// Visit the neighbors of the current vertex
for (int v = 0; v < V; ++v) {
if (graph[u][v] && !visited[v] && dist[u] != INF && dist[u] + graph[u]
[v] < dist[v]) {
// If there is a shorter path to v through u
if (dist[v] != INF) {
[Link]([Link](std::make_pair(dist[v], v)));
}
dist[v] = dist[u] + graph[u][v];
[Link](std::make_pair(dist[v], v));
}
}
visited[u] = true;
}
// Print the distances
std::cout << "Vertex\tDistance from Source" << std::endl;
for (int i = 0; i < V; ++i) {
std::cout << i << "\t" << dist[i] << std::endl;
}
}
int main() {
// Example graph represented as an adjacency matrix
std::vector<std::vector<int>> graph = {
{0, 10, 20, 0, 0, 0},
{10, 0, 0, 50, 10, 0},
{20, 0, 0, 20, 33, 0},
{0, 50, 20, 0, 20, 2},
{0, 10, 33, 20, 0, 1},
{0, 0, 0, 2, 1, 0}
};
int source = 0; // Starting vertex
dijkstra(graph, source);
return 0;
}
Vertex Distance from Source
0 0
1 10
2 20
3 23
4 20
5 21
=== Code Execution Successful ===