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.

 

 

Instruction Files

Related Questions in computer science category