 Apr 2023


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

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

 Feb 2023

www.dl.behinehyab.com www.dl.behinehyab.com

4.20
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.

(4.1a)
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.

(a) (b)Figure 4.15 Some shortest path networks.
Undergraduate, description:
Solve the allpairs shortest path problem using the FloydWarshall 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.

algorithm Dijkstra;
The Original, dumb dumb Dijkstra Algorithm

Property 4.1.
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_2P_3\) Directed Walk instead of a path, and then arising from here, it applies the none existence of negative directed cycle on the graph!

Property 4.2.
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 si 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



4.4.1. D EFINITION .
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.
