Electronics and Computer Engineering
School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet - Hanoi - Vietnam
Data structure and Algorithms
Graph
Thanh-Hai Tran
2020 2
Outline
Shortest paths
Introduction
Applications
Dijkstra’s algorithm
Minimum spanning trees
Introduction
Applications
Kruskal algorithm
2020 3
Weighted graphs
Let Gbe a weighted path, the length of a path is
the sum of the weighted of the edges of P.
If a path
A distance from a vertex v to a vertex u in G
d(v,u) is the length of the minimum length path
(shortest path) from v to uif the path exists
2020 4
Shortest Path
Given a weighted directed graph, one common
problem is finding the shortest path between two
given vertices
Recall that in a weighted graph, the length of a path
is the sum of the weights of each of the edges in that
path
Applications:
One application is circuit design: the time it takes for a
change in input to affect an output depends on the
shortest path
2020 5
Applications
http://www.hp.com/