Scribd
Upload
6 views

Data Algoritham

Daa worksheet

Uploaded by

Sharjil Sheikh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Data Algoritham

Daa worksheet

Uploaded by

Sharjil Sheikh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment 3.2
Student Name: Danish Khan UID: 21BCS3043
Branch: CSE Section/Group: 612-B
Semester: 5th Date of Performance: 23/10/23
Subject Name: Design and analysis of algorithm
Subject Code: 21CSH311

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: analyze complexity to find shortest paths in a graph with positive edge weights using
Dijkstra’s algorithm.
3. Algorithm:
• Start at your current location (point A) and set the distance to 0.
• Explore the nearby locations (connected points) and calculate the total distance from point A to
each of them.
• Choose the location with the shortest calculated distance as your next stop.
• Repeat this process, always selecting the point with the shortest total distance, until you reach your
destination (point B).

4. Code and output:

#include <iostream>
#include <vector>
#include <set>
#include <climits>
using namespace
std; const int V = 6;
int minDistance(vector<int>& dist, set<int>& sptSet) {
int min = INT_MAX, min_index; for (int v = 0; v <
V; v++) { if (!sptSet.count(v) && dist[v] <= min) {
min = dist[v];
min_index = v;
}}
return min_index;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
void printSolution(vector<int>& dist) { cout << "Vertex
\t Distance from Source\n";
for (int i = 0; i < V; i++) cout << i <<
"\t" << dist[i] << endl;
}
void dijkstra(int graph[V][V], int src) {
vector<int> dist(V, INT_MAX);
set<int> sptSet;
dist[src] = 0;

for (int count = 0; count < V - 1; count++) {


int u = minDistance(dist, sptSet);
sptSet.insert(u);
for (int v = 0; v < V; v++) { if (!sptSet.count(v) && graph[u][v] && dist[u] != INT_MAX && dist[u] +
graph[u][v] <
dist[v])
dist[v] = dist[u] + graph[u][v];
}
}

printSolution(dist);
} int main() { int
graph[V][V] = {
{0, 4, 0, 0, 0, 0},
{4, 0, 8, 0, 0, 0},
{0, 8, 0, 7, 0, 4},
{0, 0, 7, 0, 9, 14},
{0, 0, 0, 9, 0, 10},
{0, 0, 4, 14, 10, 0}
};
dijkstra(graph, 0);
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

5. Complexity: O(logn)

You might also like