8.1 Graph Traversal –Dijkstra’s Algorithm Flashcards
Shortest Path Problem Variations and Algorithms
❑Problem Variations:
❑Single-source shortest path problem: shortest paths from source node to all other nodes in the graph
❑Single-destination shortest path problem: shortest paths from all nodes in the directed graph to a single destination node.
❑All-pair shortest path problem: shortest paths between every pair of nodes in the graph
❑Various algorithms for solving the problem: Dijkstra’s algorithm, Bellman-Ford algorithm, A* search algorithm, Floyd-Warshallalgorithm etc..
Dijkstra’s Algorithm
❑Used to solve the shortest path problem
❑Both directed and undirected graphs
❑All edges must have non-negative weights
❑Graphs must be connected
❑Many variants but the most common is to find the shortest paths from a source node to all other nodes in the graph.
❑Given an end destination, we can keep track of visited nodes and thus find the path
Dijkstra’s Time Analysis
❑The complexity of the algorithm depends on the implementation and the data structure:
❑The classic implementation is O(n2), nbeing the number of nodes of the graph
❑Using other implementations like heaps: O(E + nlog n), Eis the number of edges and nis the number of nodes of the graph
What is a heap?
*In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
Dijkstra’s Algorithm Applications
*Geographical Mapping Services
▪Google Maps/Waze use algorithms similar to Dijktra’sto find the shortest path between two points
*Network Routing Protocols: find the shortest path for data packets to travel across a network
*Game Development/Robot navigation: find the shortest path for game characters to navigate around obstacles.
*Social Network Analysis: measure social influence
Dijkstra’s Algorithm Disadvantages
*No sense of direction
*It does not work with negative weights
*Once a node is marked as visited, it cannot be reconsidered even if there is another path with less cost or distance
*Time Complexity/Memory Usage for Dense Graphs: The algorithm can be quite slow on dense graphs (graphs with many edges).
*Single Source Limitation: Dijkstra’s algorithm finds the shortest path from a single source to all other vertices. If you need the shortest paths between all pairs of vertices, you must run Dijkstra’s algorithm once for each vertex, which can be inefficient.
*Not Dynamic: Dijkstra’s algorithm doesn’t adapt well to dynamic graphs where edge weights change frequently. In such cases, the algorithm would have to be rerun from scratch to find the new shortest paths
Floyd–WarshallAlgorithm
❑This algorithm computes how far each node is from every other node in the input graph
❑All-pairs shortest path
❑Computes 1-step paths, 2-step paths, etc…
❑Is it shorter to go to a node via a node rather than directly to it
?❑It does not return the paths [but it can do…]
❑Negative edges allowed (but not negative cycles)
Dynamic Programming
❑Floyd-Warshallrelies on Dynamic Programming
❑It is a problem-solving approach
❑Systematically pre-compute and store the answers to sub-problems to build up the solution to a complex problem
❑Reuses those recorded results instead of recomputing them
Dynamic Programming
A dynamic programming algorithm solves every subproblem just once and then saves its answer in a table, avoiding the work of recomputing the answer every time the subproblem is encountered.
Floyd–Warshall-Steps
❑The optimal way to represent the graph is with 2D adjacency matrix
❑If there is no edge between two nodes we set the edge weight to infinity
❑Indicating two nodes are not directly connected to each othe
Floyd–WarshallTime Analysis
❑What is the time complexity of this algorithm?
❑O(n3), where nis the number of nodes
❑Because of the three nested for loops
❑Ideal for smaller graphs ❑No larger than few hundred nodes
