We have an undirected graph *G*= [** N**,

Will the solution to this problem necessarily form a tree?

Say we really only want the shortest path from some node *s* to
a second node *t*. How could we adapt the label setting algorithm to
give this solution? How could we adapt the label-correcting algorithm to
give this solution?

Say I give you an arbitrary spanning tree. How could you test the tree to see if it is a SPT, shortest path tree?

Say we have the SPT for some root node. The tree determines a path between
every pair of nodes in ** N**. For an arbitrary pair of nodes

Say you choose a root node and find the resulting SPT. You choose the same node and use Prim's algorithm to find the MST. Say as much as you can about the difference between the two trees.

Say you have an application that requires the set of shortest paths between every pair of nodes. How could you find them?

Briefly state the difference between label setting and label correcting algorithms.

What to the labels computed for a node measure for the optimum SPT?

The label setting algorithm starts at the root node and sequentially adds edges and nodes to the tree. At some intermediate point in the algorithm we have a constructed a tree that does not span all the nodes. What can you say about the labels that have been determined by the algorithm?

For a complete network (an edge between every pair of nodes), give an order statement about the number of steps required to find the SPT with the label setting algorithm.

What if there are some edges with negative length. Will the label setting algorithm still work? Why or why not?

You have some negative length edges in your graph. Someone suggests that
you find the smallest (most negative) edge with length *d* (a negative
number). Someone suggests you add -*d* to all edge lengths and solve
that problem. Then all the arc lengths will be positive and you can use
the label setting algorithm. Will the solution to the modified problem be
the same as the original? Why or why not?

Give a mathematical programming model of the SPT problem.

Say the edges to your problem have direction. You are looking for a tree such that there is a directed path from the root node to every other node. The paths determined are to be shortest paths from the root node. Can you adapt the label setting algorithm to solve this new problem?

The label correcting algorithm given, starting with the label on the root set equal to 0 and all others set to a very large number. Is it possible to set the labels on the non-root nodes to some smaller values? Will the label correcting algorithm work for arbitrary initial labels?

Say the graph has some negative edge lengths. Although you know that the label setting algorithm may not work, you do it anyway. Starting from the label setting solution, how would you adjust the solution to find the optimum?

Say the graph has some cycle edges with a negative total length. If you perform the label setting algorithm on this graph, what will you get? If you perform the label correcting algorithm on this graph, what will you get?

How could you use a shortest path algorithm to help solve the maximum flow problem?

Say you have a directed network, *G*= [** N**,

For a given problem with nonnegative edge lengths, which algorithm is faster, the label-setting or label-correcting? Which algorithm would be easier to code for a computer? Explain your answer.