Use Bellman-Ford algorithm on G to compute the distance from every vertex of G to vertex 1. The table represents the run of the algorithm. Each row of the table corresponds to one vertex of G and each column of the table corresponds to one iteration of the algorithm. The first column contains the computed distances from each vertex of G to the vertex 1 after the initialization of the algorithm. The task is to complete the remaining columns of the table by filling out the following fields. Each field corresponds to one column (starting with the column representing the distances of the first iteration of the algorithm). To fill a field you should provide the distances of each vertex to the vertex 1 in the same order that the rows are given in the table.

part 1b) Give the shortest path, specify the vertices on a shortest path from vertex 3 to vertex 1 (provide the vertices on the path including the two endpoints in the order in which they occur on the graph separated by spaces)

part 1c) Give the shortest path tree , which arcs are part of the shortest path tree? Provide the arcs in lexicographical order separated by spaces and write an edge from a to b as a-b. For instance, if your shortest path tree contains the arc from 1 to 2 and the arc from 3 to 2, then you would write "1-2 3-2".

0 1 2 3 4 1 0 2 3 4 5 6