0
1.9kviews
Solve the following single source shortest path problem assuming vertex 5 as the source.
1 Answer
written 2.6 years ago by | • modified 2.6 years ago |
Considering the above graph The starting vertex would be 5
Step 1:- The outing edges directed 5 are
5 -> 3 {4}
5 -> 3
Step 2: - The outgoing edges directed from 3 are
3 -> 1 {10} min
3 -> 2 {20}
5 -> 3 -> 1
Step 3:- The outgoing edges directed from 1 are 1 -> 2 {15} 1 -> 4 {20}
end reached 5 -> 3 -> 1 -> 4
Hence vertex 4 will be selected. In single source shortest path if destination vertex is 4 then we have achieved shortest path 5-3-1-4 with path length 34.
4 + 10 + 20 = 34