Daa Ex-8 Mine

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 8
Student Name: Komal UID: 22BCS12451

Branch: BE-CSE Section/Group: IOT_612(B)
Semester: 5th Date of Performance: 10-10-2024
Subject Name: DAA Lab Subject Code: 22CHS-311
1. Aim: Develop a program and analyze complexity to find shortest paths in a

graph with positive edge weights using Dijkstra’s algorithm.
2. Objective: To implement and analyze the efficiency of Dijkstra’s algorithm for

finding the shortest paths in a graph with positive edge weights. The goal is to
evaluate the algorithm's time complexity based on the data structure used for the
priority queue (e.g., binary heap or Fibonacci heap).
3. Algorithm:
Step1:- Initialize:
 Create a distance array dist[] and set all values to infinity (∞) except for
the source node, which is set to 0.
 Use a priority queue (min-heap) to store nodes with their current known
shortest distance.
Step 2:- Push Source:
 Insert the source node into the priority queue with a distance of 0.
Step 3:- While Queue is Not Empty:
 Extract the node u with the minimum distance from the priority queue.
 For each neighboring node v of u, calculate the tentative distance to v
through u.
 If this distance is smaller than the current distance in dist[v], update
dist[v] and insert v into the priority queue with the new distance.
Step 4:- Repeat:
 Continue this process until the priority queue is empty.
Step 5:- Result:

DEPARTMENT OF
 At the end, dist[] contains the shortest distance from the source node to all
other nodes.
4. Implementation/Code:
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> PII; // Pair to store (distance, vertex)
// Dijkstra's algorithm to find the shortest paths from a source node

vector<int> dijkstra(int source, const vector<vector<PII>>& graph, int V) {
priority_queue<PII, vector<PII>, greater<PII>> pq; // Min-heap priority
queue
vector<int> dist(V, INT_MAX); // Initialize distances to infinity
dist[source] = 0; // Distance to the source is 0

pq.push({0, source}); // Push the source into the priority queue
while (!pq.empty()) {
int u = pq.top().second; // Get the vertex with the smallest distance
pq.pop();
// Traverse all adjacent vertices of u

for (const auto& neighbor : graph[u]) {
int v = neighbor.second;
int weight = neighbor.first;
// Relaxation step
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v}); // Push updated distance to the priority queue
}
}
}
return dist; // Return the shortest distance to all vertices

}
DEPARTMENT OF
int main() {
int V = 5; // Number of vertices
vector<vector<PII>> graph(V);
// Adding edges (weight, vertex)

graph[0].push_back({10, 1});
int source = 0; // Set the source node
// Run Dijkstra's algorithm

vector<int> distances = dijkstra(source, graph, V);
// Output the shortest distances from the source node

cout << "Shortest distances from node " << source << ":\n";
for (int i = 0; i < V; ++i) {
cout << "Node " << i << " : " << distances[i] << "\n";
}
return 0;
}
5. Output:
DEPARTMENT OF
6. Time Complexity:
Using Binary Heap: O((V + E) log V), where V is the number of vertices and E
is the number of edges.
Using Fibonacci Heap: O(E + V log V).
Space Complexity:
The overall space complexity of Dijkstra’s algorithm is O(V + E), where V is
the number of vertices and E is the number of edges.
7. Learning Outcomes:
1. Understanding of Dijkstra's Algorithm: You will learn how to implement
and apply Dijkstra’s algorithm to find the shortest paths in graphs with
positive edge weights, utilizing a priority queue for efficiency.
2. Time and Space Complexity Analysis: You will gain insights into
analyzing the time complexity (O((V + E) log V) using a binary heap) and
space complexity (O(V + E)) of the algorithm.
3. Graph Representation: You will understand how to represent graphs
efficiently using adjacency lists and handle shortest path problems with real-
world applications.

Daa Ex-8 Mine

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

Daa Ex-8 Mine

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Daa Ex-8 Mine

Uploaded by

Copyright:

Available Formats

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Student Name: Komal UID: 22BCS12451

1. Aim: Develop a program and analyze complexity to find shortest paths in a

2. Objective: To implement and analyze the efficiency of Dijkstra’s algorithm for

Step 2:- Push Source:

Step 3:- While Queue is Not Empty:

Step 4:- Repeat:

 Continue this process until the priority queue is empty.

Step 5:- Result:

using namespace std;

typedef pair<int, int> PII; // Pair to store (distance, vertex)

// Dijkstra's algorithm to find the shortest paths from a source node

dist[source] = 0; // Distance to the source is 0

// Traverse all adjacent vertices of u

return dist; // Return the shortest distance to all vertices

// Adding edges (weight, vertex)

int source = 0; // Set the source node

// Run Dijkstra's algorithm

// Output the shortest distances from the source node

You might also like