DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment-3.2
Student Name: Varun Pratap UID: 21BCS9015
Branch: CSE Section/Group: IOT_636-A
Semester: 5th Date of Performance:30/10/23
Subject Name: DAA Lab Subject Code: 21CSP-314
1. Aim: Develop a program and analyze complexity to find shortest paths in a graph with
positive edge weights using Dijkstra’s algorithm.
2. Algorithms:
Step 1: Initialize an array 'dist' of size V (number of vertices) to store the shortest distances. Set
all distances to infinity except for the source vertex, which is set to 0.
Step 2: Initialize a priority queue (min-heap) to store pairs (distance, vertex) and push (0, source)
into it. This represents the starting vertex with a distance of 0.
Step 3: While the priority queue is not empty:
Step 3a: Pop the vertex 'u' with the smallest distance from the priority queue.
Step 3b: For each neighboring vertex 'v' of 'u':
Step 3b(i): Calculate the potential new distance to 'v' as 'dist[u] + weight(u, v)'.
Step 3b(ii): If the new distance is smaller than the current distance 'dist[v]', update 'dist[v]' to
the new distance and push (new distance, 'v') into the priority queue.
Step 4: After processing all vertices or when the priority queue is empty, 'dist' contains the
shortest distances from the source vertex to all other vertices.
Step 5: Return the 'dist' array as the output.
End of Algorithm.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Define a structure to represent a weighted edge
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// Define a function to find the shortest path using Dijkstra's algorithm
vector<int> dijkstra(vector<vector<Edge>>& graph, int start) {
int V = graph.size();
vector<int> dist(V, INT_MAX); // Initialize distances to infinity
dist[start] = 0; // Distance to the start vertex is 0
// Create a priority queue for Dijkstra's algorithm
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int u_dist = pq.top().first;
pq.pop();
if (u_dist > dist[u]) continue; // Skip if we have a better path to u
for (const Edge& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
return dist;
}
int main() {
int V = 6; // Number of vertices
vector<vector<Edge>> graph(V);
// Add edges and their weights to the graph
graph[0].push_back(Edge(1, 5));
graph[0].push_back(Edge(2, 3));
graph[1].push_back(Edge(3, 6));
graph[1].push_back(Edge(2, 2));
graph[2].push_back(Edge(4, 4));
graph[2].push_back(Edge(5, 2));
graph[2].push_back(Edge(3, 7));
graph[3].push_back(Edge(5, 1));
graph[4].push_back(Edge(5, 3));
int start = 0; // Starting vertex
vector<int> shortestDistances = dijkstra(graph, start);
cout << "Shortest distances from vertex " << start << " to all other vertices:" << endl;
for (int i = 0; i < V; i++) {
cout << "Vertex " << i << ": " << shortestDistances[i] << endl;
}
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
3. Output:
4. Time complexity: O((V + E) * log(V))
