open set, closed complement and vice versa. In finite Euclidean space.

in \(\mathbb R^n\), intersections/union of open subets are still open.

Graduate based, proof. Description:

The state requires that \(s\neq t\) to be true.

By length, the question probably mean the total cost of the directed path.

(a) I think this is just a direct application of the characterization of shortest path conditions, \(d(i, j) = d(i, k) + d(k, j) \; \forall i, j \in N\). (b) I have a feeling that this is a similar proof compare to the Floyd Warshall algorithm as discussed before.

undergraduated based. Problem description:

Consider the LP formulation of the shortest path problem given on page 94 of the text. Show that shortest path problem LP is unbounded for any feasible network that has a negative cycle.

Undergraduate, description:

Solve the all-pairs shortest path problem using the Floyd-Warshall algorithm to the network given in Fig. 4.15(a). Show the distance matrix for each iteration. To make the matrix more readable, relabel the nodes a,b, ..., f for 1,2,... ,6, and z for node 0.

What the heck is this "z for node 0" under the homework discription, no such node exists in the graph, nor is thre additional nodes for the FW algorithm.

The Original, dumb dumb Dijkstra Algorithm

All Assumptions in chapter 4 applies here.

In the proof below, please observe that, the path \(P_2\) can cross with \(P_3\), therefore it said it's a \(P_2-P_3\) Directed Walk instead of a path, and then arising from here, it applies the none existence of negative directed cycle on the graph!

This is a direct applications of property 4.1.

Restate it in Clearer Mathematical Terms

Assuming that \(d(i)\) is the shortest path path length from a source node \(s\) to any other vertices: \(i\), let\(P\) denote the shortest s-i path then the following statements are equivalent: - a directed path P is a shortest path from a to k - \(d(j) = d(i) + c_{i, j}\; \forall (i, j)\in P\)

We still assume all the assumptions 4.1, 4.2, 4.3, 4.4

Definition of Compactness Remarks

Compactness is defined by the existence of converging subsequence of any sequences. The "close and boundedness" is only a characterizations of compactness when we have finite dimension Euclidean space.