Step through Dijkstra’s algorithm to calculate the single-source shortest paths from A to every other vertex.
computer science
Description
CSC
202 Assignment6 Summer’20
Legibly
write all answers and submit on Canvas by due date.
Name_______________________________________________________
•
Consider the following undirected, weighted
graph:
Lowest-cost path from A to F: A to B to C
to E to F
Step through Dijkstra’s algorithm to calculate
the single-source shortest paths from A to every other vertex.
Show your
steps in the table as presented in class meetings. Cross out old values and
write in new ones, from left to right within each cell, as the algorithm
proceeds.
Also list the vertices in the order which you
marked them known. Finally, indicate the lowest-cast path from node A to node
F.
•
Consider the following undirected, weighted
graph:
Perform Prim’s algorithm from the start node ‘A’
to find a minimum spanning tree. Draw the final MST and list the edges in the
order they are added to the MST. Write an edge as (u, v, n), where u is one of
the nodes, v is the other node, and n is the weight.
•
Run Kruskal’s algorithm by hand to build an MST
for the following graph:
Perform Kruskal’s algorithm to find a minimum
spanning tree. Draw the final MST and list the edges in the order they are
added to the MST. Write an edge as (u, v, n), where u is one of the nodes, v is
the other node, and n is the weight.
• The LZW method
achieves compression by using codes 256 through 4095 to represent
sequences of bytes. Perform the LZW compression Algorithm, as was presented in
class meeting, on the following string below: Show all steps taken…
WYS*WYGWYS*WYSWYSG
•
Bellman-Ford .
Consider the edge-weighted digraph drawn below, which has negative
weights but no negative cycles. Your task is to finish the trace below of the
Bellman-Ford algorithm, as was presented
during class meeting, for an implementation that starts with vertex A, proceeds in V phases, relaxing all of the edges in the graph in
each phase. For the purpose of this question, to relax an edge is to check for
evidence of a shorter path to its target than the best known so far, and a
successful relax is one where a shorter path is found.
The first
phase is done for you.
