The code:
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
#define MX 105
struct node {
int val;
int cost;
};
vector<node> G[MX];
bool vis[MX];
int dist[MX];
class cmp {
public:
bool operator()(node &A, node &B) {
if (A.cost > B.cost) return true;
return false;
}
};
void dijkstra(int source) {
priority_queue<node, vector<node>, cmp> PQ;
PQ.push({source, 0});
while (!PQ.empty()) {
node current = PQ.top();
PQ.pop();
int val = current.val;
int cost = current.cost;
if (vis[val] == 1) continue;
dist[val] = cost;
vis[val] = 1;
for (int i = 0; i < G[val].size(); i++) {
int nxt = G[val][i].val;
int nxtCost = G[val][i].cost;
if (vis[nxt] == 0) {
PQ.push({nxt, cost + nxtCost});
}
}
}
}
int main() {
// Initialize the graph with provided edges
G[0].push_back({1, 9});
G[0].push_back({2, 3});
G[1].push_back({2, 7});
G[1].push_back({4, 6});
G[2].push_back({3, 1});
G[2].push_back({5, 3});
G[3].push_back({4, 4});
G[3].push_back({5, 4});
G[4].push_back({6, 9});
G[5].push_back({7, 7});
G[6].push_back({7, 5});
G[6].push_back({8, 6});
G[7].push_back({8, 3});
// Source node (change as needed)
int source = 0;
dijkstra(source);
cout << "Shortest distances from node " << source << ":\n";
for (int i = 1; i <= 8; i++) {
cout << "To node " << i << ": " << (dist[i] == INT_MAX ? -1 : dist[i]) << endl;
}
// Print the shortest path from the first index to the last index
cout << "Shortest path from node 0 to node 8: " << dist[8] << endl;
return 0;
}
Output:
Code:
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int destination;
int weight;
Edge(int dest, int w) : destination(dest), weight(w) {}
};
class Graph {
public:
int vertices;
vector<vector<int>> adjMatrix;
Graph(int V) : vertices(V), adjMatrix(V, vector<int>(V, 0)) {}
void addEdge(int src, int dest, int weight) {
adjMatrix[src][dest] = weight;
adjMatrix[dest][src] = weight;
}
void primMST() {
vector<int> parent(vertices, -1);
vector<int> key(vertices, INT_MAX);
vector<bool> inMST(vertices, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int startVertex = 0;
pq.push({0, startVertex});
key[startVertex] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
inMST[u] = true;
for (int v = 0; v < vertices; ++v) {
int weight = adjMatrix[u][v];
if (!inMST[v] && weight > 0 && weight < key[v]) {
key[v] = weight;
parent[v] = u;
pq.push({key[v], v});
}
}
}
// Print the MST
int totalWeight = 0;
cout << "Minimum Spanning Tree:\n";
for (int i = 1; i < vertices; ++i) {
cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << "\n";
totalWeight += key[i];
}
cout << "Total Weight of MST: " << totalWeight << "\n";
}
};
int main() {
Graph g(9);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 3);
g.addEdge(1, 2, 7);
g.addEdge(1, 4, 6);
g.addEdge(2, 3, 1);
g.addEdge(2, 5, 3);
g.addEdge(3, 4, 4);
g.addEdge(3, 5, 4);
g.addEdge(4, 6, 9);
g.addEdge(5, 7, 7);
g.addEdge(6, 7, 5);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 3);
g.primMST();
return 0;
}
Output:
Code:
Output:
