Scribd
Upload
83 views4 pages

DAA Worksheet-3.2 20BCS7611

The document describes an experiment implementing Dijkstra's algorithm to find the shortest paths in a graph with positive edge weights, with steps including marking all vertices as unvisited initially, calculating path lengths from the source and updating if smaller, and repeating until all vertices are marked visited to build the shortest path tree. The code implements Dijkstra's algorithm on a sample graph to obtain the shortest distances from the source to all other vertices.

Uploaded by

AYUSH TIWARI
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
83 views4 pages

DAA Worksheet-3.2 20BCS7611

The document describes an experiment implementing Dijkstra's algorithm to find the shortest paths in a graph with positive edge weights, with steps including marking all vertices as unvisited initially, calculating path lengths from the source and updating if smaller, and repeating until all vertices are marked visited to build the shortest path tree. The code implements Dijkstra's algorithm on a sample graph to obtain the shortest distances from the source to all other vertices.

Uploaded by

AYUSH TIWARI
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/ 4

Experiment 3.

Student Name: Ayush Tiwari UID: 20BCS7611


Branch: CSE Section/Group: 905-B
Semester: 5 th Subject Code: 20CSP 312
Subject Name: DAA Lab

------------------------------------------------------------------------------------------------------------------------------------
1. Aim/Overview of the practical:

Code and analyze to find the shortest paths in a graph with positive edge weights
using Dijkstra’s algorithm.

2. Task to be done/which logistics used:


In this program we will generate a SPT (shortest path tree) with a given source as
a root.
Maintain two sets, one set contains vertices included in the shortest-path tree,other
set includes vertices not yet included in the shortest-path tree. At every step of
thealgorithm, find a vertex that is in the other set (set not yet included) and has a
minimumdistance from the source.

3. Algorithm/Flowchart :
1) First of all, we will mark all vertex as unvisited vertex
2) Then, we will mark the source vertex as 0 and all other vertices as infinity
3) Consider source vertex as current vertex
4) Calculate the path length of all the neighboring vertex from the current vertex by
adding the weight of the edge in the current vertex
5) Now, if the new path length is smaller than the previous path length then replace it
otherwise ignore it
6) Mark the current vertex as visited after visiting the neighbor vertex of the current
vertex
7) Select the vertex with the smallest path length as the new current vertex and go
back to step 4.
8) Repeat this process until all the vertex are marked as visited.
4.Steps for experiment/practical/Code:

#include <iostream>
using namespace std;
#include <limits.h>
#define V 9
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}

void printSolution(int dist[])


{
cout << "Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << " \t\t\t\t" << dist[i] << endl;
}

void dijkstra(int graph[V][V], int src)


{
int dist[V];

bool sptSet[V];

for (int i = 0; i < V; i++) dist[i] =


INT_MAX, sptSet[i] = false;

dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[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, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);
return 0;
}

5.Observations/Discussions/ Complexity Analysis:

Time Complexity: O(V2)


6.OUTPUT:

Learning outcomes(what I have Learnt) –


1.Learnt to find the shortest paths in a graph with positive edge weights using
Dijkstra’s algorithm.

2. Learnt to optimize code and use Dijkstra’s algorithm’s application.

You might also like