91Ó°ÊÓ

You are given a directed graph with (possibly negative) weighted edges, in which the shortest path between any two vertices is guaranteed to have at most edges. Give an algorithm that finds the shortest path between two vertices u and v in $\mathbf{O}\left(K\left|E\right|\right)$time.

Give an algorithm that takes as input a directed graph with positive edge lengths, and returns the length of the shortest cycle in the graph (if the graph is acyclic, it should say so). Your algorithm should take time at most $\mathbf{O}\left|V^3\right|$.

Give an $\mathbf{O}{\left|V\right|}^{\mathbf{2}}$algorithm for the following task.

Input:An undirected graph $\mathbf{G}\mathbf{=}\left(V,E\right)$; edge lengths ${\mathbf{I}}_{\mathbf{e}}\mathbf{>}\mathbf{0}$;an edge $\mathbf{e}\mathbf{∈}\mathbf{E}$.

Output:The length of the shortest cycle containing edge e

You are given a strongly connected directed graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}\mathbf{}$ with positive edge weights along with a particular${\mathbf{v}}_{\mathbf{0}}\mathbf{∈}\mathbf{V}$ . Give an efficient algorithm for finding shortest paths between all pairs of nodes, with the one restriction that these paths must all pass through${\mathbf{v}}_{\mathbf{0}}$ _.

Shortest paths are not always unique: sometimes there are two or more different paths with the minimum possible length. Show how to solve the following problem in $\mathit{O}\mathbf{\left(}\mathbf{\right(}\mathbf{\left|}\mathit{V}\mathbf{\right|}\mathbf{+}\mathbf{\left|}\mathit{E}\mathbf{\right|}\mathbf{)}\mathbf{}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{|}\mathit{V}\mathbf{|}\mathbf{}\mathbf{)}$time.

Input:An undirected graph $\mathbf{}\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathit{E}\mathbf{)}$;edge lengths ${\mathit{l}}_{\mathbf{e}}\mathbf{>}\mathbf{0}$; starting vertex $\mathit{s}\mathbf{∈}\mathit{V}$.

Output:A Boolean array for each node u , the entry $\mathit{u}\mathit{s}\mathit{p}\mathbf{\left[}\mathit{u}\mathbf{\right]}$should be $\mathit{t}\mathit{r}\mathit{u}\mathit{e}$ if and only if there is a unique shortest path s to u (Note:$\mathit{u}\mathit{s}\mathit{p}\mathbf{\left[}\mathit{s}\mathbf{\right]}\mathbf{=}\mathit{t}\mathit{r}\mathit{u}\mathit{e}$)

In cases where there are several different shortest paths between two nodes (and edges have varying length),the most convenient of these paths is often the one with fewest edges. Forinstance, if nodes represent cities and edge lengths represent costs of flying between cities, theremight be many ways to get from cityto city t which all have the same cost. The mostconvenientof these alternatives is the one which involves the fewest stopovers. Accordingly, for a specific starting node S , define

$best\left[u\right]=$minimum number of edges in a shortest path from S to u .

In the example below, thebestvalues for nodes $S,A,B,C,D,E,F$are $0,1,1,1,2,2,3$, respectively.

Give an efficient algorithm for the following problem.

Input:Graph $G=\left(V,E\right)$; positive edge lengths $l_e$; starting node $s∈V$.

Output: The values of $best\left[u\right]$ should be set for all nodes$u∈V$

Generalized shortest-paths problem.In Internet routing, there are delays on lines but also, more significantly, delays at routers. This motivates a generalized shortest-paths problem.

Suppose that in addition to having edge lengths $\left\{\left\{I_e:e∈E\right\}\right\}$ ,a graph also has vertex costs $\left\{c_V:v∈V\right\}$ . Now define the cost of a path to be the sum of its edge lengths, plusthe costs ofall vertices on the path (including the endpoints). Give an efficient algorithm for the followingproblem.

Input:A directed graph $\mathit{G}\mathbf{=}\left\{V,E\right\}$ positive edge lengths ${\mathbf{I}}_{\mathbf{e}}$ and positive vertex costs ${\mathit{c}}_{\mathbf{v}}$; a starting vertex $\mathit{s}\mathbf{∈}\mathit{v}$.

Output:An array $\mathit{c}\mathit{o}\mathit{s}\mathit{t}[.]$ such that for every vertex $\mathit{u}\mathbf{,}\mathit{c}\mathit{o}\mathit{s}\mathit{t}\left[u\right]$, is the least cost of any path from s to u (i.e., the cost of the cheapest path), under the defnition above.

Notice that $\mathit{c}\mathit{o}\mathit{s}\mathit{t}\left[s\right]\mathit{=}\mathit{c}$.

Suppose Dijkstra’s algorithm is run on the following graph, starting at node A.

a) Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm.

b) Show the final shortest-path tree.

There is a network of roads G=(V,E) connecting a set of cities . Each road in E has an associated length ${\mathbf{I}}_{\mathbf{e}}$. There is a proposal to add one new road to this network, and there is a list E' of pairs of cities between which the new road can be built. Each such potential road localid="1659075853079" $\mathit{e}\mathbf{\text{'}}\mathbf{}\mathbf{∈}\mathit{E}\mathbf{\text{'}}$ has an associated length. As a designer for the public works department you are asked to determine the road localid="1659075866764" $\mathit{e}\mathbf{}\mathbf{\text{'}}\mathbf{∈}\mathit{E}\mathbf{\text{'}}$whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.

Shortest path algorithms can be applied in currency trading. Let ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}{\mathit{c}}_{\mathbf{n}}$ be various currencies; for instance, ${\mathit{c}}_1$might be dollars, ${\mathit{c}}_{\mathbf{2}}$pounds, and ${\mathit{c}}_{\mathbf{3}}$ lire.

For any two currencies ${\mathit{c}}_{\mathbf{i}}$ and ${\mathit{c}}_{\mathit{j}}$ , there is an exchange rate ${\mathit{Ï„}}_{\mathbf{i}\mathbf{,}\mathbf{j}}$; this means that you can purchase ${\mathit{Ï„}}_{\mathbf{i}\mathbf{,}\mathbf{j}}$ units of currency ${\mathit{c}}_{\mathbf{j}}$ in exchange for one unit of ${\mathit{c}}_{\mathbf{j}}$. These exchange rates satisfy the condition that ${\mathit{r}}_{\mathbf{i}\mathbf{j}}\mathbf{.}{\mathit{r}}_{\mathbf{j}\mathbf{i}}\mathbf{<}\mathbf{1}$ so that if you start with a unit of currency ${\mathit{c}}_{\mathbf{j}}$, change it into currency and then convert back to currency localid="1658917254028" ${\mathit{c}}_{\mathbf{i}}$, you end up with less than one unit of currency ${\mathit{c}}_{\mathbf{i}}$ (the difference is the cost of the transaction).

The exchange rates are updated frequently, rejecting the demand and supply of the various currencies. Occasionally the exchange rates satisfy the following property: there is a sequence of currencies ${\mathit{c}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{c}}_{\mathbf{i}\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{c}}_{\mathbf{i}\mathbf{k}}$such that ${\mathit{r}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{r}}_{\mathbf{i}\mathbf{2}\mathbf{.}\mathbf{i}\mathbf{3}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{r}}_{\mathbf{i}\left(k-1\right)\mathbf{,}\mathbf{i}\mathbf{k}\mathbf{,}}{\mathit{r}}_{\mathbf{i}\mathbf{k}\mathbf{+}\mathbf{1}}\mathbf{>}\mathbf{1}$. This means that by starting with a unit of currency ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$and then successively converting it to currencies ${\mathit{c}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{c}}_{\mathbf{i}\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{c}}_{\mathbf{i}\mathbf{k}}$, and finally back to ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$, you would end up with more than one unit of currency ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$ . Such anomalies Last only a fraction of a minute on the currency exchange, but they provide an opportunity for risk-free profits.