Dijkstra Algorithm (single source shortest path)
Initial graph
Dijkstra Algorithm (single source shortest path)
• Next step is select the vertice with smallest cost (2)
• Check the connections for that vertice and modify them with
relaxation.
Dijkstra Algorithm (single source shortest path)
Dijkstra Algorithm (single source shortest path)
Drawback of the Dijkstra Algorithm
Dijkstra may or may not work for negative edges.
Dymamic Programming
Dymamic Programming
• Greedy method and dynamic programming are methods to solve optimization problems.
• The purposes are same; to get the minimum or maximum result.
• In greedy method, the procedure that followed must be optimal. (Exp. Kruskal’s always select the
edge with minimum cost)
• In dynamic programming, all possible solutions must be try out and optimal solution is selected.
• This is time comsuming than the greedy method
• Dynamic programming problems mostly solved by using recursive formulas.
• Though not using recursion of programming (generally iterative), but the formulas are recursive.
• Dynamic programming follows principle of optimality. Problems solved by sequence of decisions.
• In greedy method decision is taking one time, in dynamic programming decision is taken in every
stage.
• Dynamic programming adopts tabulation method and memoization method.
Fibonacci Numbers
We can reduce function of calls, because same function
Recursive version of Fibonacci series calls more than one times with same parameters
Memoization‐top down approach
Tabulation‐bottom up approach
• Directed weighted graphs,
Vertices divided into stages,
vertices connected to one stage to next
stage only
First (starting point) and last (ending point)
stage has only one vertice.
• Important to represent resource allocation
• Objective of the problem is selecting the
path has minimum cost between source
and sink.
• It is a minimization problem and can be
solved with dynamic programming.
• Dynamic programming works on principal
on optimality. (Sequence of decision)
• If I started from S(1), I have select one of
the vertices from stage 2.
• If I select 5, there are two options ( 7 and
8).
• Optimal solution has to be selected.
• On every stage, a decision must be taken.
(optimality holes principle)
Sequence of decision
shortest path from
source to sink, two
paths with same cost
• Cost is calculated
from source to sinc
in forward method
• So, first start with
sinc point.
cost adjacency matrix
All Pairs Shortest Path (Floyd‐Warshall)
All Pairs Shortest Path (Floyd‐Warshall)
Matrix Chain Multiplication
Matrix Chain Multiplication
Matrix Chain Multiplication
Matrix Chain Multiplication
Matrix Chain Multiplication
Matrix Chain Multiplication
Matrix Chain Multiplication
Single Source Shortest Path Problem (Bellman Ford)
• Directed weighted graph with
negative edges
• To find the shortest path from
source to all nodes.
• Revlaxation n‐1 times.
• n=|V|‐1
• All possible paths must be covered.
Single Source Shortest Path Problem (Bellman Ford)
• Result of the first pass
Single Source Shortest Path Problem (Bellman Ford)
Result of the second pass
Single Source Shortest Path Problem (Bellman Ford)
Result of the third pass No changes cost of the vertices
after third pass.
In a complete graph, there must
be an edge between every pair
of vertices.
Complexity of bellman ford for
complete graph is O(n3) .
Bellman Ford Algorithm
Bellman Ford Algorithm
After 3 relaxation
After an extra
relaxation there are
changes, because of
the total negative
cost of the cycle.
0/1 Knapsack Problem
0/1 Knapsack Problem
0/1 Knapsack Problem
0/1 Knapsack Problem
0/1 Knapsack Problem
0/1 Knapsack Problem
0/1 Knapsack Problem‐Sets Method
Traveling Salesman Problem ‐ Dynamic Programming using Formula
Traveling Salesman Problem ‐ Dynamic Programming using Formula
Traveling Salesman Problem ‐ Dynamic Programming using Formula
Traveling Salesman Problem ‐ Dynamic Programming using Formula
Traveling Salesman Problem ‐ Dynamic Programming using Formula
Traveling Salesman Problem ‐ Dynamic Programming using Formula