djikstrasalgorithm-250418064637-830a84e1.pptx

dijkastara algorithm

1. Subject: Discrete Mathematics and Graph Theory Title: Djikstra’s Algorithm application Submitted To: Prof. Aman Mukti Presented by: 1) Shraddha Shukla –SA258 2) Suraj Bhandare – SA260 3) Aliza Malgi – SA203

2. What is Shortest path algorithm? The shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the edges weights is minimum. In simpler words, To solve the shortest path problem means to find the shortest possible route or path between two vertices (or nodes) in a Graph. Some Common Algorithms: Dijkstra's Algorithm Bellman-Ford Algorithm Floyd- Warshall Algorithm A\* Algorithm

3. Dijkstra's algorithm finds the shortest path from one vertex to all other vertices. It does so by repeatedly selecting the nearest unvisited vertex. The algorithm works on weighted graphs , where edges have associated costs (e.g., distances, time, etc). Dijkstra's algorithm is a greedy algorithm, which means that it goes for most optimal solution available next and combines all of them. This algorithm does not accept non- negative edges and works only if edges have positive cost assigned to it. This algorithm is single source. Introduction to Djikstra’s Algorithm

4. Some common terminologies Graph: A collection of vertices and edges, where vertices are interconnected by edges. Vertices (or Nodes): Represent locations or points in the graph. Edges: Connecting link between vertices and having a specific weight or cost. Weighted Graph: A graph where each edge has an associated weight or cost. Source Node: The starting node from where shortest path calculation starts. Shortest Path: The path with the least total weight (cost or distance) between two nodes. 7. Distance: The weight or cost associated with an edge. Initialization: Setting initial distances to vertices, typically infinity for all except the source, which starts at 0. Visited: A vertex that has been considered as part of the shortest path from the source. Unvisited: A vertex that has not yet been considered as part of the shortest

5. Problem statement 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 No of Nodes - 6 No of Edges - 9 Source node -

6. 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 Unvisited nodes = {0,1,2,3,4,5,6} 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 Unvisited nodes = {1,2,3,4,5,6}

7. 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 Adjacent nodes = 1,2 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 → 1 weight = 2 Unvisited nodes = {2,3,4,5,6} Adjacent nodes = 2 weight = 6 We must visit all unvisited nodes before arriving to our next node 3 Unvisited nodes = {3,4,5,6}

8. 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 Adjacent node = 3 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 → 1 → 3 = 7 → 2 → 3 = 14 Hence we take least weight path Unvisited nodes = {4,5,6} Adjacent nodes = 5,4 → 1 → 3 → 4 = 17 → 1 → 3 → 5 = 22 Hence we choose node 4 Unvisited nodes = {5,6}

9. 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 → 1 → 3 → 4 → 5 = 23 → 1 → 3 → 4 → 6 = 19 Hence we take least weight path Unvisited nodes = {5} Next node = 5 → 1 → 3 → 4 → 5 = 23 → 1 → 3 → 5 = 22 → 1 → 3 → 4 → 6 → 5 = 25 Least weight = 22 Unvisited nodes = {} Adjacent nodes = 5,6

10. 1 2 3 5 6 4 2 6 5 8 10 15 2 6 6 Final Graph We now have shortest distance path to every node in the graph from the source node. Supposedly we have to go from to 6 then the path would be → 1 → 3 → 4 → 6 with total weight 19

11. Complexity Time complexity: O(E Log V). Where E represents the edges and V represents the vertices. Space complexity: O(V).

12. Navigation C Maps – Finds the shortest or fastest routes in GPS systems like Google Maps and Waze. Network Routing – Used in internet protocols (e.g., OSPF) to determine efficient paths for data transmission. Transportation C Logistics – Optimizes delivery routes and travel paths in systems like public transit or shipping. Game Development C AI – Helps game characters or robots navigate maps and avoid obstacles intelligently. Emergency C Urban Planning – Assists in planning city layouts and emergency response routes for quick access. Real - world applications

13. Benefits and Limitations BENEFITS: It is used to find the shortest path in a graph. It is widely used in geographical mapping systems. It is used to pinpoint the graph vertices on a map. It is used to determine the Open Shortest Path First in IP routing. It is utilized in telephone networks to establish connections. LIMITATIONS: It performs a blind search, which can be time- consuming. It can't handle negative edges, resulting in acyclic graphs where the optimal shortest path may not be found.

14. Dijkstra’s Algorithm is a powerful and efficient method for finding the shortest path in graphs with non- negative edge weights. Its simplicity, accuracy, and wide range of real- world applications— from GPS navigation to network routing— make it a fundamental tool in computer science. Despite some limitations, such as not handling negative weights, it remains one of the most widely used and taught algorithms CONCLUSION