Course Code : MCS-021 Course Title Assignment Number Data and File Structures BCA(IID/021/Assignment/2023-24 Maximum Marks 100 Weightage 30% Last Dates for Submission : 31 October, 2023 (For July Session) : 30" April, 2024 (For January Session) This assignment has 10 questions of 8 Marks each, answer all questions. Rest 20 marks are for viva voce. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. au. 2. Q@. Qs. Quo. Elaborate various asymptotic notations used to evaluate the efficiency of th (8) Write a program that accepts two polynomials as input and displays the resultant polynomial after multiplication of input polynomials 8) Write a C programme to implement a doubly linked list. Also write functions to perform insertion and deletion operations in it 8) What is a Circular Queue? Write an algorithm to perform insertion and deletion operation in a Circular Queue 8) Write a program in C for insertion sort. Write the step-by-step working of the insertion sort for the following set of data: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4. Also count the number of swaps and comparison operations performed for it 8) Write a detailed note on file organization techniques. 8) Create the binary tree for which the in-order and post order traversal are given as below: @) In-order: QUVTMPSYZXR. Post-order: VUTQZYXSRPM Create a B tree of order-S for the following keys, inserted in the sequence. @) 25,5, 10, 2, 3.35, 10, 50, 55, 60, 12, 18, 20, 1 Further, delete the keys 1, 2, 10, and 12. Show all the intermediate steps. Create AVL tree for the following keys inserted in the order: 8) 5,15, 3,25, 10, 2, 35, 7, 45, 30, 12, 20, 14 7, and 8. Show all the intermedia Further, delete the keys 2, steps. Solve the following instance of single source shortest paths problem with vertex‘ as the source using suitable method. 8)Copyright with Kunj Publication only Not for resale Course Code: MCS-021 Course Title: Data and File Structures Assignment Number: BCA (III)/021/Assignment/2023-24 DisclaimertSpecil Nore: These ae jut he somple of the AnswerfSolations 0 some ofthe Questions given in the Assignments. These Sample Answerolutns are prepared by Private TeacherTusor urs forthe help an uldanceof he suden to get am ideo howe Ifthe can anever the Questions sven the Asignents We donot lain 10% accuracy of these sample anewer as these are based on he nol aa capability of Private TeacherTuto. Sample ansiers may be sen asthe Guldeep forthe tference to prepare the ‘ancwers ofthe question given in the assignment As thee solutions and answers are prepared bythe private TeacherTwor so he chances ‘fervor or mistake cannot be denied. Any Omission or Ervor is highly regretied though every care hasbeen hen whe preparbg these ‘Sample Answer Solutions Please conul our own Teacher/Tuor before you prepare apartictar Answer av for up-to-date and ext !nformason, data and soluhon.Staden should mus ea and refer the fica tay. material proved by the univer This assignment has 10 questions of 8 Marks each, answer all questions. Rest 20 marks are for viva voce. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. QI. Elaborate various asymptoti@ notations) used to evaluate the efficiency of thi algorithm, Asymptotic notations are mathematical tools used to analyze and compare the efficiency of algorithms in computer science. They help us understand how the algotithin’speFforinance grows With the input size, giving usan ide of how it Will behave for large inputs. The three most commonly used asymptotic notations are: 1, Big O Notation (O-notation) Big O notation describes the upper bound or worst-case scenario of an algorithm's time complexity. It provides an upper limit on the growth rate of the algorithm's running time Concerning the input size. In other words, it gives an approximation of how the algorithm's performance scales with the worst possible input. Mathematically, for a function f(n), we say f{(n) is O(g(n)) if there exist positive constants C and n0 such that 0 < fin) < C * g(n) for all n> nO. In simple terms, fn) is bounded by the function g(n) up to a constant factor for sufficiently large values of n. For example, if an algorithm has a time complexity of O(n42), it means the algorithm’s running time grows quadratically with the input size n. 2. Omega Notation (Q-notation): Omega notation describes the lower bound or best-case scenario of an algorithm's time complexity. It provides a lower limit on the growth rate of the algorithm's running time concerning the input size. In other words, it gives an approximation of how the algorithm's performance scales with the best possible input.Copyright with Kunj Publication only Not for resale Mathematically, for a function f{(n), we say f{n) is Q(g(n)) if there exist positive constants C and n0 such that 0 < C * g(n) < f(n) for all n> n0. In simple terms, f(n) is, bounded from below by the function g(n) up to a constant factor for sufficiently large values of n, For example, if an algorithm has a time complexity of O(n), it means the algorithm's running time grows linearly with the input size n in the best-case scenario. 3. Theta Notation (@-notation): ‘Theta notation provides a tight bound on an algorithm's time complexity, capturing both the upper and lower bounds. It gives a range within which the algorithm's performance will fall concerning the input size. Mathematically, for a function f{(n), we say f{n) is @(g(n)) if there exist positive constants C1, C2, and n0 such that 0.>Ghr* g(n) < f{n) < C2 * g(n) for all n> n0. In simple terms, f(n) is bounded’ both from above and below by the function g(n) up to constant factors for sufficiently large values of n. For example, ifan algorithm has a time complexity of @(n), it means the algorithm's running time grows linearly with the input size n in both the best and worst-case scenarios, In summary, these asymptotic notations help us analyze find compare the efficiency of algorithms based on how their running times grow as the input size increases. They allow Us to make informed decisions when Choosing the most appropriate algorithm fora specific problem. Q2. Write a program thal accepts two polynomials as input and displays the resultant polynomial after multiplication of input polynomials. Python program that multiplies two polynomials and displays the resultant polynomial. We will represent polynomials as lists of coefficients, where the index of the list corresponds to the power of the variable. For example, the polynomial 3x*2 + 2x + 1 will be represented as [3, 2, 1]. Here's the Python program: def multiply_polynomials(poly 1, poly2): result_degree = len(poly |) + len(poly2) - 2 # Degree of the resultant polynomial # Initialize the result list with zeros result_poly = [0] * (result_degree + 1)# Perform multiplication of the two polynomials for iin range(len(poly1)): for j in range(len(poly2)): result_poly(i + j] += poly![i] * poly2{j] return result_poly def display_polynomial(poly): degree = len(poly) - 1 "CR PUBLICATION elif degree -i== 1: ALL US:- polynomial_str polynomial_str += str(coefficient) if i < degree: polynomial_str + print(polynomial_str) if _name__ == "__main_": # Input polynomials as lists of coefficients (highest power to lowest power)Copyright with Kunj Publication only Not for resale F” poly! = list(map(int, input("Enter the coefficients of the first polynomial (separated by space): ").split)) poly2 = list(map(int, input("Enter the coefficients of the second polynomial (separated by space): ").split())) +# Multiply the input polynomials result = multiply_polynomials(poly1, poly2) # Display the resultant polynomial print("Resultant polynomial after multiplication: display_polynomial(result) You can run this program and enter the coefficients of the two polynomials when prompted. The program will then multiply the two polynomials and display the RUNPBB: deletion operations: #include struct Node { int data; struct Node* prev; struct Node* next; bk / Function to create a new node struct Node* createNode(int data) {Copyright with Kunj Publication only Not for resale Ph. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Memory allocation failed!\n"); exit(1); } newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; void insertAtBeginning( struct Node** head, int CONFPUBLICATION (Phead)->prev = newNode; ALL US:- vy - // Function to insert a new node at the end of the list void insertAtEnd (struct Node** head, int data) { struct Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; } else { struct Node* temp = “head; while (temp->next != NULL) (Copyright with Kunj Publication only Not for resale Ps... temp = temp->next; } temp->next = newNode; newNode->prev = temp; // Function to delete a node from the list void deleteNode(struct Node** head, int key) { if (*head == NULL) { printf("List is empty!\n"); PUBLIGAD ui p laa ALL US:- ‘ return; if (temp == NULL) { printf("Node with data %d not found!\n", key); return; if (temp->prev != NULL) { temp->prev->next = temp->next: } else { *head = temp->next;Copyright with Kunj Publication only Not for resale if (temp->next != NULL) { temp->next->prev = temp->prev; free(temp); // Function to display the doubly linked list void display(struct Node* head) { struct Node* temp = head; KONE PUBLICATION rintf(\n"); ALL US:- = a // Function to free the memory allocated for the list void freeList(struct Node head) { struct Node* temp; while (head != NULL) { temp = head; head = head->next; free(temp);Copyright with Kunj Publication only Not for resale P. int main) { struct Node* head = NULL; insertAtEnd(&head, 10); insertAtBeginning(&head, 5); insertAtEnd(&head, 20); insertAtBeginning(&head, 2); insert AtEnd(&head, 30); display(head); deleteNode(&heady'5); deleteNode(&head, 30); display head); freeList(head); return 0; This C program creates a doubly linked list, provides functions to insert nodes at the beginning and end of the list, delete nodes with a specific data value, and displays the list before and after deletion operations. Note that the program also includes a function to free the dynamically allocated memory used for the list. Q4. What is a Circular Queue? Write an algorithm to perform insertion and deletion operation in a Circular Queue A Circular Queue is a data structure that represents a circular buffer, similar to a regular queue, but with a fixed size. It uses an array to store elements, and when the queue becomes full, it wraps around and starts reusing the empty slots from the beginning of the array. This circular behavior allows for efficient memory utilization and avoids shifting elements during insertions and deletions, unlike a regular linear queueCopyright with Kunj Publication only Not for resale PI To implement a Circular Queue, you need to keep track of two pointers: "front" and “rear.” The "front" pointer points to the first element in the queue, and the "rear" pointer points to the last element. Initially, both pointers are set to -1. When the queue is empty, "front" and "rear" both point to -1. For each insertion, the "reat" pointer is incremented, and for each deletion, the "front" pointer is incremented. Here's the algorithm to perform insertion and deletion operations in a Circular Queue: 1, Initialize the Circular Queue: + Set the maximum size of the Circular Queue (MAX_SIZE + Create an array of size MAX_SIZE to hold the elements. + Initialize front and rear pointers to -1 . Check if the Circular Queue is empty: + If front and rear both are -1, the queue is empty. . Check if the Circular Queue is full: + If (reat +1) % MAX_SIZE == front, the queue is full. . Insertion Operation (Enqueue): « Cheek if the queue is full. ‘+ If it’s full, return an error of handle it accordingly. + Increment the rear pointer: rear = (rear +1) % MAX_SIZE. + Insert the element at the rear position: queue[rear) = element. . Deletion Operation (Dequeue): +. Checkiif the queue is empty. Ifit's empty, return an error or handle it accordingly. Get the element to be dequeued: dequeuedElement = queue[front].. If front and rear are pointing to the same element (ie., there's only one clement in the queue), reset both pointers to -1. Otherwise, increment the front pointer: front = (front + 1) % MAX _SIZE. Return the dequeuedElement. Here's a Python implementation of the Circular Queue: class CircularQueue: def __init__(self, max_size):self.queue = [None] * self. MAX_SIZE. self.front = self.rear = -1 def is_empty(self): return self.front == -1 and self.rear =: def is_full(self): return (self.rear + 1) % self. MAX_SIZE, def enqueue(self, element): if self.is_full0: KUK def dequeue(self): if self.is_empty(): print("Circular Queue is empty. Unable to dequeue.") return None dequeued_element = self.queue[self.front] if self.front == self.rear: self.front = self.rear = -1 else: self-front = (self.front + 1) % self: MAX_SIZE return dequeued_elementPublication only Not for resale You can create an instance of the CircularQueue class, set the maximum size, and then perform insertion (enqueue) and deletion (dequeue) operations on it. QS. Write a program in C for insertion sort. Write the step-by-step working of the insertion sort for the following set of data: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4. Also count the number of swaps and comparison operations performed for it. C program for insertion sort, along with the step-by-step working and the count of, swaps and comparisons for the given set of data. include 11 Function to perform insertion sort void insertionSort(int arr{}, int n, int “swaps, int *comparisons) { inti, key, j for (i = 1; i < nyi il: KUNJ PUBLICATION /Move elements of arr{0..i-1] th Her than key to ane poston ahead of it Current position hile G@>=0 && ars + 1) = ari; (swaps); j=i-1 ) (*comparisons)++; arr{j + 1] =key; // Function to print the arrayCopyright with Kunj Publication only Not for resale void printArray(int arr[], int n) { for (int i = 0; i 10) Swaps: | (25 moves to the right of 10) Array: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4 Step 3: 2nd pass - Insertion of 86: ‘Comparisons: 1 (86 > 25) Swaps: | (86 moves to the right of 25) Array: 10, 25, 86, 1, 16, 95, 37, 56, 5, 15, 20, 4 Step 4: 3rd pass - Insertion of I: Comparisons: 2 (1 < 86, L-<25) Swaps: 2 (86 and 25.move to the right) Array: 10, 25/86, 86, 16, 95, 37, 56, 5, 15, 20, 4 Step 5: 4th pass - Insertion of 16: Comparisons: 2 (16 < 86, 16 > 25) Swaps: 1 (86 moves to the right of 25) Array: 10, 25, 25, 86, 16, 95, 3756, 5, 15, 20, 4 Step 62 Sth pass~ Insertion of 95: Comparisons: 2 (95 > 86, 95 > 25) Swaps: 0 (No swaps) Array: 10, 25, 86, 95, 16, 95, 37, 56, 5, 15, 20, 4 Step 7: 6th pass - Insertion of 37: Comparisons: 3 (37 < 95, 37 > 86, 37 > 25) Swaps: 2 (95 and 86 move to the right) Array: 10, 25, 37, 86, 95, 95, 37, 56, 5, 15, 20, 4 Step 8: 7th pass - Insertion of 56: Comparisons: 3 (56 < 95, 56 > 86, 56 > 37) Swaps: | (95 moves to the right of 37)Copyright with Kunj Publication only Not for resale Array: 10, 25, 37, 56, 86, 95, 37, 56, 5, 15, 20, 4 Step 9: 8th pass - Insertion of 5: Comparisons: 4 (5 < 95, 5 < 86, 5 < 56,5 > 37) Swaps: 3 (95, 86, and 56 move to the right) Array: 10, 25, 37, 56, 86, 95, 95, 86, 56, 15, 20, 4 Step 10: 9th pass - Insertion of 15: Comparisons: 4 (15 < 95, 15 < 86, 15 < 56, 15 > 37) Swaps: 3 (95, 86, and 56 move to the right) Array: 10, 25, 37, 56, 86, 86, 95, 56, 56, 15, 20, 4 Step 11: 10th pass - Insertion of 20: Comparisons: 5 (20 < 95, 20 <,86720 < 56, 20 $56, 20 > 37) Swaps: 4 (95, 86, 56, and'56 move to the right) Array: 10, 25,37,56, 86, 86, 95, 95, 56, 56, 20, 4 Step 12: | Ith pass - Insertion of 4: Comparisons: 6 (4 < 95, 4 < 86, 4 < 56,4 < 56,4 < 20, 4.< 56) Swaps: 595, 86, 56, 56, and 20 move tothe right) Atay: 10, 25, 37, 56, 86, 86, 95, 95, 56, 56,20, 4 ‘The final sorted array is:/l, 4, 5, 10, 15, 16, 20, 25, 37, 56, 86, 95 Number of swaps: 21 Number of comparisons: 38 Q6. Write a detailed note on file organization techniques. File organization techniques refer to the methods and structures used to store and manage data within computer systems. These techniques are crucial for efficient data retrieval, storage, and maintenance. Different file organization techniques are employed depending on the specific requirements of the application, the type of data, and the expected access patterns. Here are some of the common file organization techniques: 1. Sequential File Organization: In a sequential file organization, data is stored in a continuous sequence, one after another. Each record has a fixed length, and records are accessed sequentially from the beginning to the end of the file. It is, suitable for applications with frequent sequential access patterns, such as batchCopyright with Kunj Publication only Not for resale. processing systems. However, random access to records is inefficient, as the system must scan through all preceding records to reach the desired one. Advantages: + Simple and easy to implement. + Efficient for sequential processing and processing large volumes of data. Disadvantages: + Inefficient for random access. + Insertions and deletions can be time-consuming. 2. Indexed Sequential File Organization: This technique combines aspects of sequential and indexed file organization. The file contains a primary index that stores key values and their corresponding disk addresses (pointers) to the actual data records. The primary index:is:typically sorted, allowing for efficient binary search to locate'the desired record's address. Once the address is found, the system cam tise sequential access to retrieve the record itself. Advantages: +) Efficient for both sequential and random aecess’ + Suitable for applications with varying access patterns. Disadvantages: + Requires additional overhead to maintain the index. + Insettions and deletions may require index updates, potentially causing performance issues. Direct (Hash) File Organization: The direct file organization, also known as hash file organization, uses a hash function to calculate the storage location of a record based on its key value. The hash function generates an address for each record, and data is stored at these calculated addresses. This technique allows for quick access to records based on their keys. Advantages: + Fast access for records with known keys. + Suitable for applications requiring quick data retrieval. Disadvantages: + Can lead to collisions (different records getting the same address), which requires handling through overflow areas or chaining. + Inefficient for range queries or sorting the records based on keys.Copyright with Kunj Publication only Not for resale ~ 4. Indexed File Organization: In indexed file organization, an index table is maintained separately from the main data file. This table contains key values and their corresponding disk addresses. The index table allows for efficient lookup of record addresses, enabling quick access to desired records. Advantages: + Efficient for random access and retrieval based on keys. + Changes in the main data file do not require frequent updates to the index table. Disadvantage: + Requires extra storage space for the index table. + Insertions and deletions may require updates to the index, impacting performance. B-Tree and B+Tree File Organization: B-trees and B+trees are balanced tree structures used for organizing large amounts of data. They are commonly employed in database management systems and file systems. These trees maintain data in a hierarchical structure, allowing for efficient searching, insertion, and deletion operations. Advantages: + Efficient for large datasets, + Provides balanced access times for both sequential and random access. + Suitable for databases and file systems. Disadvantages: + Complex implementation and maintenance + B-trees may waste some space in nodes, affecting storage efficiency. Each file organization technique has its strengths and weaknesses, making them suitable for different use cases. Understanding the access patterns and requirements of the application is crucial in selecting the appropriate file organization technique to ensure optimal data management and retrieval. Q7. Create the binary tree for which the in-order and post order traversal are given as below: In-order: QUVTMPSYZXR Post-order: VUTQZYXSRPM To construct the binary tree using the given in-order and post-order traversals, we can follow the following steps:Copyright with Kunj Publication only Not for resale . The last element in the post-order traversal will always be the root of the binary tree. . Find the root in the in-order traversal. . Elements to the left of the root in the in-order traversal will form the left subtree. |. Elements to the right of the root in the in-order traversal will form the right subtree. . Recursively apply steps 1 to 4 to construct the left and right subtrees. Let's construct the binary tree using the given in-order and post-order traversals: In-order: QUVTMPSYZXR. Post-order: VUTQZYXSRPM Step 1: The lastelement of post-order is 'M’, which will be the root of the binary tree. Step 2: Find the root 'M' in the in-order traversal. The elements to the left of 'M' will form the left subtree, and the elements to the right will form the right subtree. In-order: QUVT MPSYZXR Post-order: VUTQZYX SRPM Step 3: Recursively construct the left and right subtrees. For the left subtree: In-order: QUVT Post-order: VUTQ For the right subtree: In-order: PSYZXR Post-order: ZYXSRP_Copyright with Kunj Publication only Not for resale PI Step 4: Continue recursively constructing the left and right subtrees. Left subtree: In-order: QU VT Post-order: V TQ Right subtree: In-order: PS YZXR Post-order: Z YXSR P. Step 5: Continue recursive! ind right subtrees. Now, we have constructed the binary tree. Let's represent it:So, the binary tree that matches'the given in-ordérand post-order traversals is as shown above To create’a B-tree of order 5 for the given keys'and perform the specified deletions, follow these steps 1. Insertion: + Start with/an empty B. ‘Insert the keys in the given sequence: 25, 60, 12, 18, 20, 1. 5, 30, 50, 55, 2. Deletion: + Delete the keys 1, 2, 10, and 12 from the B-tree. Let's go through the steps one by one: Step I: Insertion Initially, the B-tree is empty. We start by inserting the keys in the given sequence: Insert 25Insert 5: ery Insert 10: CMe) Insert 2; Insert 35: Insert 45Insert 30: Insert 55: Insert 60: Insert 12:Insert 18: Insert 20: Step 2: Del Now, we will delete the keys 1, 2,10, and 12 from the B-tree: Delete 1: (Nothing to delete as 1 is not present in the B-tree) Delete 10:Note: The B-tree has been rearranged after the deletions to maintain the B-tree properties. let's create the AVL tree step by step for the given keys and then proceed with the deletions. An AVL tree is a self-balancing binary search tree, so at each step, we need to ensure that the balance factor of each node is within the range of -1, 0, or I. If it's not, we perform rotations to balance the tree, Step L: Insert 5 Step 2: Insert 15Step 3: Insert 3 va PantsStep 7: Insert 35 Step 8: Insert 7 Ta camer INN Pane Step 10: Insert 30Step 11: Insert 12 Step 12: Insert 20Step 13: Insert. 14. aN Eure awn PREC an ce) Now that we have the AVL tree, let's proceed with the deletions:Step 14: Delete 2 Step 16: Delete 7Step 17: Delete 8 (Since 8 is not in the tree, nothing will be changed.) The AVL tree is now balanced and contains the keys: 3, 10, 14, 20, 25, 30, 35, 45. QUO. Solve the following ifistance of single sourée shortest paths problem with vertex ‘a’ as the soufce using suitable method. To solve the single-source shortest path problem with vertex 'a’ as the source, we can use Dijkstra’s algorithm, Dijkstra’s algorithm finds the shortest paths from a given source vertex to all other vertices in a weighted graph. Let's start by organizing the given graph and assigning initial distances to each vertex from the source ‘a boa For convenience, we'll use the letter in parentheses to represent each vertex: (b)---=(a)----(1)--=-(6)---(10)---(8)----(d) ----(€)---(6)---(6)---(@)Copyright with Kunj Publication only Not for resale . s) Now, let's initialize the distance from ‘a' to each vertex. We'll set it to infinity for all vertices except ‘a’ (distance of 'a' to itself is 0): (3)--=-(b)--(@*)---(1)-+--(@)--(10)--(8)oo--(d)--=-(6)>-=-(6)--=-(6)---(0) mo 0 0 m7 0 0 0 0 mw wo w Next, well iteratively explore the neighboring vertices and update their distances from ‘a’ if we find shorter paths. We repeat this process until we have found the shortest path to alll vertices. 1. First step: Explore neighbors of 'a' (vertex 'b’ and vertex 'I') and update their distances: « Distance from ‘a’ t 1 (update the distance) + Distance from ‘a’ to 'I': 6 (update the distance) B)—-(b)-—@") 1) (6) —--(10)--(8)-(A-(0)---(6)--6)-(0) 2 1 PG 0 0 ow wo wm ey wo 2. Second step: Explore neighbors of ’b' (vertex '3' and yertex ‘a') and update their distances: + Distance from ‘a’ to '3': 1 + 3 =4 (update the distance). + Distance from 'a' to ‘a’: 1+ (update the distance) 34) 1b G01) (6) (10) -8)—-(@)--(0)---(6) (6) 4 10 6 © © © BD DB Hw . Third step: Explore neighbors of 'I' (vertex 'a’ and vertex ‘6') and update their distances: Distance from 'a' to ‘a’: 6 (no update) Distance from ‘a’ to '6': 1 + 6 = 7 (update the distance) (3*) 4b") (a) —-(1)---(6")-(10)8)-—-()-—-(0)--(6)-(6)-e) 41 6 7m 07 0m» © ©Copyright with Kunj Publication only Not for resale . Fourth step: Explore neighbors of '6' (vertex 'I’, vertex '10', vertex 'e', and vertex ‘a') and update their distances: Distance from ‘a’ to 'I': 6 (no update) Distance from 'a' to '10': 1 + 10 = 11 (update the distance) Distance from 'a' to 'e': | + 6 = 7 (update the distance) (3%) (6%) (a) 14)--(64)-- (10) (8) ---(d)--—-()----(6)-(68)-(e*) 4 1 0 6 7 Th © © © © F Fifth step: Explore neighbors of '10' (vertex '6', vertex '8', and vertex 'd') and update their distances: Distance from 'a' to '6: 7 (no update) Distance from ‘a! to'8': 1 + 10 = 11 (no update) Distance from ‘a! to '': 1 +L =Ls(update the distance) BO) A6-—(10)-B)--(-()-() (64) Le) 41 Ug) 11 w» 11 wo .. Sixth step: Explore neighbors of 'd’ (vertex '10!, vertex ‘c’. and vertex '8’) and update their distances: Distance from ‘a’ to '10': 11 (no update) Distance from 'a' to ''c': 1 + 1L= 12 (update the distance) Distance from ‘a! to'8': L411 = 12 (no update) B-Ab —(@)—-(1)(69)-—(10) (8) (0) (6) 16)-—(6*) Ce) SA ae eee pe ogee eae . Seventh step: Explore neighbors of 'c' (vertex ‘d’, vertex ‘6’, and vertex ‘e’) and update their distances: Distance from ‘a’ to 'd’: 11 (no update) Distance from ‘a’ to '6': 7 (no update) Distance froma’ to 'e': 7 (no update) (3*)---(b*)-—-(a 1*)---(6*)---(10*)--(8)----(d*)---(c*)---(6") 41 Meee lide too ae Deed ete ee:yright with Kunj Publication only Not for resale Pk Now, all vertices have been visited and we have found the shortest distances from vertex ‘a’ to all other vertices in the graph. The final result is as follows: Shortest distance from 'a' to 'a’: Shortest distance from 'a' to Shortest distance from 'a' to ‘ Shortest distance from 'a' to ‘d': Shortest distance from ‘a’ to 'e': 7 Shortest distance from ‘a’ to" Shortest distance from 'a' to ‘6: Shortest distance from ‘a’ to’ Shortest distance from 'a' to '10': 11 Shortest distance from 'a' to Thus, the solution to the single-source shortest path problem with vertex ‘a’ as the source is complete. KUNJ PUBLICATION