Short Answer - Shortest Path Tree

We have an undirected graph G= [N, E], where N is the set of nodes and E is the set of edges. Each edge is defined by a node pair (i, j). Each edge has a nonnegative length. We are trying to solve the problem of finding a set of paths from some root node s to every other node in the graph. Each path found is to be the shortest path. We have two algorithms to solve this problem, the label setting algorithm and the label-correcting algorithm.

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 i and j, is the path a shortest path?

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, A], where the set A is a set of directed arcs. Each arc k has a lower bound on flow equal to zero, a finite upper bound equal to uk, and a unit cost for flow equal to ck. One node s is designated as a source node and a second node, t, is designated as a sink node. We want to find a flow solution that delivers the flow v from s to t. The solution is to minimize total cost. Suggest a way to use the shortest path algorithm to find this solution.

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.

Return To Problems