Shortest Path Problems

Prove Theorem 1: Dijkstra's algorithm finds the SD from a fixed vertex $(v)$ to any vertex $i$ in the network if there is a path from $v$ to $i$.

Using Dijksra's algorithm, find a shortest distance arborescence rooted at vertex 1 of the directed network shown in Fig. 5-8.

Fig. 5-8

Using Dijkstra's algorithm, find a shortest distance arborescence for the network whose weight matrix is

Prove Theorem 5.2: The Floyd-Warshall algorithm using the triangle operation correctly solves the SD and SP problem.

Find the SD matrix and the SP matrix of the network in which the weight matrix $A$ is

Find the SD matrix and the SP matrix of the network for which the weight matrix is

In Problem 5.6, find an SP from vertex 4 to vertex 2.

Construct a shortest distance arborescence rooted at vertex 1 in the network of Problem 5.6, the path matrix.

Suppose the negative entry ( -1 ) that appears in the fourth column of the weight matrix in problem 5.6 is replaced by a smaller negative entry ( -3 ). Find a negative cycle in the modified network.

In Problem 5.6, obtain the distance matrix and the path matrix that will give the shortest distance between every pair of vertices using paths that will not use vertices 5,6, and 7 as intermediate vertices. Use these two matrices to obtain a path of minimum length from vertex 7 to vertex 4 that does not use vertices 5 and 6 as intermediate vertices.

Prove Theorem 3: Let $\left\{ 1,2,3, \ldots , n\right\}$ be the vertex set of the complete graph $G$ with a nonnegative weight function $w$ satisfying the triangle property $w(\left\{ i, j\right\} ) \leq w(\left\{ i, k\right\} )+w(\left\{ k, j\right\} )$ for any three vertices $i, j$, and $k$. If $W$ is a set of $m$ vertices in network $G$, there exists a Steiner tree for $W$ in the network that contains at most $(n-2)$ Steiner points.

Find a Steiner tree for the set $W=\left\{ 1,2,3,4\right\}$ in the network shown in Fig. 5-4.

Find the Steiner points of the set $\left\{ 1,3,5\right\}$ in the network of Problem 5.5.

Find the median of the network of Problem 5.5.

Find the weighted median of the network of Problem 5.5 if the weights of the vertices are $1,0,3,3,3$, 1, and 2, respectively.

Find the center of the network of Problem 5.5.

In a network, the minimum value of the eccentricity is the radius $\boldsymbol {r}(\boldsymbol {G})$, and the maximum value is the diameter $\boldsymbol {d}(\boldsymbol {G})$. Show that $r(G) \leq d(G) \leq 2 r(G)$.

Show that if each edge of a tree has a nonnegative weight, the cardinality of its center (median) is at most 2.

List the arcs of the shortest distance arborescence rooted at vertex 1 of the network with $V=\left\{ 1,2,3,4,5,6\right\}$ and $E=\left\{ (1,2),(1,3),(1,4),(2,3),(2,5),(3,6),(4,5),(5,6)\right\}$ with weights $4,7,3,3,2,2,3$, and 2, respectively.

List the arcs of the shortest distance arborescence rooted at vertex 1 of the network with $V=\left\{ 1,2,3,4,5,6\right\}$ and $E=\left\{ (1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5),(4,6),(5,3)\right\}$ with weights $3,7,7,2,5,3,2,5$, and 1, respectively.

Find the SD matrix $A_{5}$ and the SP matrix $P_{5}$ of the undirected network with $V=\left\{ 1,2,3,4,5\right\}$ and $E= \left\{ \left\{ 1,2\right\} ,\left\{ 1,5\right\} ,\left\{ 2,3\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} ,\left\{ 4,5\right\} \right\}$ with weights $1,4,5,1,2$, and 1, respectively.

Find the SD matrix and the SP matrix of the network with the following weight matrix:

Find the weight of a Steiner tree of the set $\left\{ 1,2,3\right\}$ in the network whose weight matrix is