SIT221 Assignment for Data Structure and Algorithms.

Running head: SIT221 Assignment for Data Structure and Algorithms
SIT221 Data Structures and Algorithms
Name of The Student
University of Affiliation

Running head: SIT221 Assignment for Data Structure and Algorithms
Practical Task 9.1
1. Consider the graph that is directed G = (V,E) represented in the following cost
adjacency matrix:
Solution For the question
Diagram of the single-source-shortest path problem
Starting vertex
2 2 3
A B F H
1 5
9 10 2 1
4 C 11 3 G
2 1
D 7 E
To find the shortest distance, from (Busato & Bombieri, 2015) we have to
repeat the process of increasing a group of vertices which have short distances that are
already known. The vertex which will not be in this our set will contain a best-fit
distance for now. Something to not is that every vertex has a cost which represent the
shortest or suitable distances.
The best way of finding a single-source path that is short in our graph we have
created, we have to develop a simple dijkstra algorithm. Assumption is that we have
no weight that have no edges.
i. For every vertex V, we define and initialize it to V.cost = ∞ and V.discovered =
FALSES.
ii. Next we set Starting.cost = 1
iii. Since we have undiscovered vertices in the graph,
a) We choose the undiscovered vertex V that contain the lowest cost
b) Do the marking on vertex V as discovered
c) Now for every edge (V,U) that has weight

Running head: SIT221 Assignment for Data Structure and Algorithms
Solution from the single-source-shortest path
0 2 4 7
2 2 3
A B F H
1 5
9 10 2 1
4 C 11 3 G
2 1 8
D 7 E
4 11
vertices Discovered? Cost_obtained paths
A yes 0
B yes 2 A
C yes 1 A
D yes 4 A
E yes 11 G
F yes 4 B
G yes 8 H
H yes 7 F
The Order that is Added to the discovered Set:
A,C,B,D,F,H,G,E
2. P being the shortest path from a given vertex s to another vertex t on a graph. In
case the weight is increased by one on the graph, what will be the effect on the
shortest path s to t?.
Solution
The shortest path according to Popa & Popescu,(2016) may change
depending on the multiplier value but for this scenario, it will not change because of
multiplier being 1. This is because, there could be a possibility of having a
differentiated number on the edges in different path from s to t. For instance, let our
path that is shorter contain weight 20 and has 10 edges. We could have another
weight with 4 edges and a whole weight 50. The weight of the path that is shortest

Running head: SIT221 Assignment for Data Structure and Algorithms
will be increased by 1*10 thereby becoming 20 + 10. Weight of the other path will
increase by 4*1 and becomes 50+4. So the shortest path will be 30 which is still the
same.(Panitanarak & Madduri,2014, July)
3. Consider the directed graph based diagram with G = (V,E) which is represented by
the cost adjacent matrix:
Draw the graph and solve the single-source-shortest distance of path challenge using
an algorithm known as Bellman-Ford’s algorithm.