Shortest Path Algorithm, Greedy
Algorithm And Dijkstra's
Algorithm
Group members: Hrijan Shahi, Rohan Shrestha
Sujit Thakur, Sajal thapa
Introduction to Shortest Path
Algorithms
Shortest path algorithms are fundamental in
graph theory and computer science.
They are used to find the minimal distance
between nodes in various applications such as
GPS navigation.
This presentation will cover the concepts of
shortest path algorithms, greedy algorithms,
and Dijkstra's algorithm.
What is a Shortest Path
Algorithm?
A shortest path algorithm is designed to
find the shortest route between two
points in a graph.
These algorithms can handle various
types of graphs, including weighted and
unweighted graphs.
Common applications include network
routing, urban planning, and logistics
optimization.
What is a Greedy Algorithm?
A greedy algorithm makes the best
choice at each step with the hope of
finding the global optimum.
This approach does not always
guarantee the best overall solution but
is often efficient and straightforward.
Greedy algorithms are commonly used
in optimization problems, such as
scheduling and resource allocation.
Characteristics of the Greedy Method:
Greedy Choice Property
At each step, the algorithm makes the best possible choice (locally optimal) with the hope that this
leads to a globally optimal solution.
It doesn’t reconsider choices once made.
Optimal Substructure
A problem has an optimal substructure if an optimal solution to the problem contains optimal
solutions to its sub problems.
This is a critical requirement for greedy algorithms to yield correct results.
No Backtracking
Once a decision is made, it is never changed (unlike backtracking or dynamic programming).
This leads to faster execution but may not always give the correct solution.
Efficient Time Complexity
Greedy algorithms are generally faster and simpler than other approaches like dynamic
programming.
Commonly have time complexity of O(n log n) or O(n) depending on the problem.
Not Always Optimal
The greedy approach does not guarantee an optimal solution for all problems.
Examples of Greedy
Algorithm Applications
• Activity Selection Problem
• Fractional Knapsack Problem
• Huffman Coding
• Prim’s and Kruskal’s Algorithms (for MST)
• Dijkstra’s Algorithm (with a priority queue)
Introduction to Dijkstra’s
Algorithm
Dijkstra's algorithm is a specific greedy
algorithm used to find the shortest path
from a source node to all other nodes in a
graph.
It works on both directed and undirected
graphs with non-negative edge weights.
The algorithm was proposed by computer
scientist Edsger W. Dijkstra in 1956.
How Dijkstra’s Algorithm
Works
Dijkstra’s algorithm starts by initializing
the distance to the source node as zero
and all other nodes as infinity.
It repeatedly selects the node with the
smallest known distance, updates its
neighbors, and marks it as visited.
This process continues until all nodes
have been visited or the shortest path to
the target node is found.
Algorithm steps
1. Set distance of all nodes to ∞, source node to 0.
2. Add all nodes to a priority queue.
3. While the queue is not empty:
- Extract node with the smallest distance.
- For each neighbor, calculate tentative distance:
newDist = currentDist + edgeWeight
- If newDist is smaller, update the neighbor’s distance.
4. Repeat until all nodes are visited.
Pseudo code:
function Dijkstra(Graph, source):
create a min-priority queue Q
for each vertex v in Graph:
distance[v] = ∞
previous[v] = null Q.insert(v, distance[v])
distance[source] = 0
Q.decrease_key(source, 0)
while Q is not empty:
u = Q.extract_min() for each neighbor v of u:
alt = distance[u] + weight(u, v)
if alt < distance[v]:
distance[v] = alt
previous[v] = u
Q.decrease_key(v, alt)
return distance[], previous[]
Time Complexity
Implementation Time Complexity
.
Array / Matrix O(V²)
Min-Heap +
O((V + E) log V)
Adjacency List
Fibonacci Heap O(E + V log V)
Advantages:
1. Efficient for Single-Source Shortest Path
Dijkstra's algorithm efficiently finds the shortest path from a single source node to all
other nodes in a weighted graph with non-negative weights.
2. Works Well with Greedy Strategy
It uses a greedy approach, selecting the closest unvisited node at each step, which leads
to an optimal solution for graphs with non-negative edge weights.
3. Applicable to Many Real-World Problems
It’s used in GPS systems, network routing protocols (like OSPF), game AI, and transport
planning — wherever shortest path calculations are needed.
4. Optimal with Non-Negative Weights
When edge weights are non-negative, Dijkstra’s guarantees the shortest path without the
need to backtrack or re-evaluate nodes.
5. Can Be Optimized with Data Structures
Its performance improves significantly when using min-heaps (priority queues) and
adjacency lists, especially in sparse graphs.
Limitations:
Doesn’t Work with Negative Edge
Weights
Not Suitable for All-Pairs Shortest
Path
Greedy – Can’t Backtrack
Can Be Inefficient on Dense Graphs
No Built-In Path Recovery
Applications
GPS Navigation Systems
-Network Routing Protocols (e.g., OSPF)
-Google Maps and Delivery Apps
Robotics & Game AI for Pathfinding
Conclusion and Future
Directions
Understanding shortest path algorithms
is essential for solving real-world
problems involving networks and
graphs.
While Dijkstra’s algorithm is powerful,
research continues into more efficient
algorithms for specific classes of graphs.
Future developments may include
integrating artificial intelligence to
enhance pathfinding in complex and
dynamic networks.
