0% found this document useful (0 votes)
10 views

Lecture 9-Graph-Part 2-Shortest Path Algorithms

File
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
10 views

Lecture 9-Graph-Part 2-Shortest Path Algorithms

File
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 52

GRAPHS

Part 2 - Shortest Path


Algorithms
Pg.2 / 52

 Single-pair shortest paths. Path from a single vertex


to another one.

 Dijkstra  Single-source shortest paths.

 Bellman-Ford  Single-source shortest paths (havi


ng negative edges).

 Floyd-Warshall  All-pairs shortest paths.

2
Pg.3 / 52

The shortest path algorithms are effected by:

 Directed/Undirected graphs.
 Weights of the edges (positive or negative).
 Representation of the graph in the memory, matrix
or a linked list (effecting the performance).
 Single or all pairs paths.
 Dense or sparse graphs...

3
Pg.4 / 52

4
Pg.5 / 52
Shortest Path

Unweighted path length is simply the number of


edges on the path, namely N-1.
5
Pg.6 / 52
Single-Source Shortest Path Problem

Given as input a weighted graph, G = (V,E), and a disti


nguished vertex, s, find the shortest weighted path fro
m s to every other vertex in G.
2
v1 v2
4 1 3 10

2 2
v3 v4 v5

8 4 6
5
1
v6 v7

Shortest (Weighted) Path from V1 to V6 is: v1, v4, v7, v6. Cost = 6

6
Pg.7 / 52

Single-Source Shortest Path Algorithms

We will examine different algorithms:

1) Unweighted shortest path algorithm


2) Weighted shortest path algorithm

Assuming no negative edges.

7
Pg.8 / 52

1. Weighted Shortest Paths


Pg.9 / 52
Weighted Shortest Paths
 Dijkstra’s Algorithm
– Example of a greedy algorithm
– Do the best thing in each step.
 At each state, the algorithm chooses a vertex v, w
hich has the smallest distance to s(d[v]) among all
the unknown vertices.
– Then, the adjacent nodes of v (which are denoted as u)
are updated with new distance information.

9
Pg.10 / 52

10
Pg.11 / 52

11
Pg.12 / 52

12
Pg.13 / 52
Using Array Data Structure

13
Pg.14 / 52

14
Pg.15 / 52

15
Pg.16 / 52

16
Pg.17 / 52

17
Pg.18 / 52

18
Pg.19 / 52

19
Pg.20 / 52

20
Pg.21 / 52

21
Pg.22 / 52

22
Pg.23 / 52

23
Pg.24 / 52

24
Pg.25 / 52

Shortest Path Example: Using Heap Structure

Weighted Directed Graph G is shown!

2
v1 v2
4 1 3 10

2 2
v3 v4 v5

8 4 6
5
1
v6 v7

We are interested in all shortest paths to all nodes from node v1

25
Pg.26 / 52

Initial Configuration

Previous node
vertex known Distance to S
(parent)
v1 F 0 0
v2 F ∞ 0
v3 F ∞ 0
v4 F ∞ 0
V5 F ∞ 0
V6 F ∞ 0
V7 F ∞ 0

26
Pg.27 / 52

0 ∞
2
v1 v2
4 1 3 10

2 2
v3 v4 v5 ∞
∞ V1 0
8 4 6
5
1
v6 v7
∞ ∞

27
Pg.28 / 52

V4 1
0 2
2
v1 v2 V2 2
4 1 3 10

2 2
v3 v4 v5 ∞
1
8 4 6
5
1
v6 v7
∞ ∞

28
Pg.29 / 52

0 2 V2 2
2
v1 v2
4 1 3 10 V5 3
3
2 2
v3 v4 v5 3 V3 3
1
8 4 6 V7 5
5
1
v6 v7
9 5

29
Pg.30 / 52

V5 3
0 2
v1 2 v2 V3 3
4 1 3 10
3
2 2 V7 5
v3 v4 v5 3
1
8 4 6
V6 9
5
v6 1 v7
9 5

30
Pg.31 / 52

0 2
2
v1 v2
V3 3
4 1 3 10
3
2 2 V7 5
v3 v4 v5 3
1
V6 9
8 4 6
5
1
v6 v7
9 5

31
Pg.32 / 52

0 2
v1 2 v2
10
V7 5
3 4 1 3

v3 2 v4 2 v5 3 V6 8
1
8 4 6
5
v6 1 v7
8
9 5

32
Pg.33 / 52

0 2
2
v1 v2
4 1 3 10
3 V6 6
2 2
v3 v4 v5 3
1
8 4 6
5
1
v6 v7
8 6 5

33
Pg.34 / 52

0 2
2
v1 v2
4 1 3 10
3
2 2
v3 v4 v5 3
1
8 4 6
5
1
v6 v7
6 5

Finished! Empty Heap

34
Pg.35 / 52
Final Configuration

vertex known Distance to S Previous node


v1 T 0 0
v2 T 2 v1
v3 T 3 v4
v4 T 1 v1
V5 T 3 v4
V6 T 6 v7
V7 T 5 v4

35
Pg.36 / 52

2. Un-weighted Shortest Paths

36
Pg.37 / 52
Unweighted Shortest Paths
v1 v2

v3 v4 v5

v6 v7

 Assume all edges are unweighted.


 We are interested in all shortest paths to all nod
es from a given node, s.

37
Pg.38 / 52

38
Pg.39 / 52

39
Pg.40 / 52

40
Pg.41 / 52

41
Pg.42 / 52

42
Pg.43 / 52

43
Pg.44 / 52
Example
• Assume that we want to find out all the shortest paths to
all nodes from node v3.

v1 v2

v3 v4 v5

v6 v7

44
Pg.45 / 52

Vertex Adjacent Vertices


v3 v1, v6

1
v1 v2

v3 v4 v5

v6 v7

45
Pg.46 / 52

Vertex Adjacent Vertices


v1 v2, v4

2
v1 v2

S 1

v3 v4 v5

0 2
1
v6 v7

46
Pg.47 / 52

Vertex Adjacent Vertices


v2 v 4, v 5

2
v1 v2

S 1

v3 v4 v5 3

0 2
1
v6 v7

47
Pg.48 / 52

Vertex Adjacent Vertices


v4 v6, v7

2
v1 v2

S 1 3
v3 v4 v5

0 2
1
v6 v7

48
Pg.49 / 52

Vertex Adjacent Vertices


v5 v 4, v 7

2
v1 v2

S 1

v3 v4 v5 3

0 2
1
v6 v7

49
Pg.50 / 52

Vertex Adjacent Vertices


v6 none
v7 v6
2
v1 v2

S 1

v3 v4 v5 3

0 2
1
v6 v7

3
50
Pg.51 / 52

Algorithm – Initial Configuration


vertex known Distance to S Previous node

v1 F ∞ 0

v2 F ∞ 0

v3 F ∞ 0

v4 F ∞ 0

V5 F ∞ 0

V6 F ∞ 0

V7 F ∞ 0

51
Pg.52 / 52
Last Configuration

vertex known Distance to S Previous node

v1 T ? ?

v2 T ? ?

v3 T ? ?

v4 T ? ?

V5 T ? ?

V6 T ? ?

V7 T ? ?

52

You might also like