Scribd
Upload
17 views4 pages

Ex - No:10 Implementation of Dijkstra Algorithm and Dynamic Programming Date

The document outlines the implementation of Dijkstra's algorithm for finding the shortest path in a graph and the use of dynamic programming to find the Longest Common Subsequence. It includes the aim, algorithms, pseudocode, and confirms the successful execution of both programs. The results indicate that the outputs for both algorithms have been verified.

Uploaded by

22D011 AROCKIAVIMALJAPSON A
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
17 views4 pages

Ex - No:10 Implementation of Dijkstra Algorithm and Dynamic Programming Date

The document outlines the implementation of Dijkstra's algorithm for finding the shortest path in a graph and the use of dynamic programming to find the Longest Common Subsequence. It includes the aim, algorithms, pseudocode, and confirms the successful execution of both programs. The results indicate that the outputs for both algorithms have been verified.

Uploaded by

22D011 AROCKIAVIMALJAPSON A
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

Ex.

No:10 IMPLEMENTATION OF DIJKSTRA ALGORITHM AND DYNAMIC


Date: PROGRAMMING

Aim:

(a) To write a program to implement Dijkstra’s algorithm for finding the


shortest path.
(b) To write a program to find the Longest Common Subsequence using
dynamic programming
Algorithm:
 Dijkstra’s Algorithm:
1. Get the input graph using adjacency matrix
2. Select the source and destination vertex
3. Apply Dijkstra algorithm and finalize the vertices with minimum cost.
4. Output the path and its minimum distance
 Dynamic Programming:
i. Initialize a 2D array dp of size (m+1) x (n+1) with all values as 0, where m =
len(X) and n = len(Y).
ii. Fill the table:
iii. If X[i-1] == Y[j-1], then dp[i][j] = dp[i-1][j-1] + 1
iv. Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
v. The final answer will be dp[m][n], i.e., the bottom-right cell.

PSEUDOCODE:
 Dijkstra’s Algorithm:
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0

while Q IS NOT EMPTY


U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]

PROGRAM:
OUTPUT
Result:
Thus the program to implement Dijkstra’s algorithm to find the shortest path of a graph
and to implement Dynamic programming to determine the Longest Common
Subsequence are executed and the outputs are verified.

You might also like