Problema 4

\textbf{Problema 4.}\\
\textbf{a.} Notăm $U^F_j(k)$, $U^B_j(k)$, $S(k)$, $T(k)$, $U^F_j$, $U^B_j$, $S$, $T$ la iterația $k$.\\

$m_1(k) = min_{j \in V - S(k)}U^F_j$ \tab $m_2(k) = min_{l \in V - T(k)}U^B_l$\\\\
Demonstrăm că $m_1(k) \leq m_1(k+1)$ $\forall k \geq 1$.\\\\
$N_1(k) = \{ j \in V - S(k+1) | U^F_j(k) = U^F_j(k+1)$\}\\
$M_1(k) = \{ j \in V - S(k+1) | U^F_j(k) \neq U^F_j(k+1)$\}\\\\
$m_1(k+1) = min_{j \in V - S(k+1)} U^F_j(k)$ \\

$= min \{ min_{j \in N_1(k)} U^F_j(k+1), min_{j \in M_1(k)} U^F_j(k+1) \}$\\

$= min \{ min_{j \in N_1(k)} U^F_j(k), min_{j \in M_1(k)} U^F_j(k+1) \}$\\\\
$N_1(k) \subseteq V - S(k)$ $\Rightarrow$ $min_{j \in N_1(k)} U^F_j(k) \geq min_{j \in V - S(k)} U^F_j(k)  = m_1(k)$\\\\
$min_{j \in M_1(k)} U^F_j(k+1) = min_{j \in M_1(k)} \{ U_j^F(k) + a_{j^*j}(k) | j \in M_1(k) \}$ $\geq$
$min_{j \in M_1(k)}\{U_j^F(k)\}$ \\$\geq$
$min_{j \in V - S(k)} U_j^F(k) = m_1(k)$\\

$\Rightarrow$ $m_1(k+1) \geq m_1(k)$, analog $m_2(k+1) \geq m_2(k)$\\

$\Rightarrow$ $min_{j \in V - S}U_j^F, min_{l \in V - S}U_l^F$ nu descresc.\\\\
\textbf{b.}
Demonstrăm prin inducție $a(S,S_2,...S_n), \forall U_{S_n}^F, \forall S_2, ..., S_n \in S$\\
\tab \textbf{1)}
$a(S, S_2) = U_{S_2}^F$\\
\tab \textbf{2)}
Presupunem $a(S, ..., S_k) \geq U_{S_k}^F, \forall S_2, ..., S_k \in S$\\
Demonstrăm că $a(S, ..., S_{k+1}) \geq U_{S_{k+1}}, \forall S_2, ..., S_{k+1} \in S$\\
În iterație avem $if(U_{S_{n+1}}^F > U_{S_n}^F + a_{S_n S_{n+1}})\tab
U_{S_{n+1}}^F = U_{S_n}^F + a_{S_n S_{n+1}}$\\

$\Rightarrow U_{S_{k+1}}^F \leq U_{S_k}^f + a_{S_k S_{k+1}} \leq a(S, ..., S_k) + a_{S_k S_{k+1}} = a(S, ..., S_{k+1})$\\

Analog $a(T_n, ..., T) \geq U_{T_n}^F, \forall T_2, ..., T_{n-1} \in T$\\
Fie $a(P_{st}) = a(S, ..., jj', ..., l'l, ..., T) = a(S, ..., j) + a(j', ..., l') + a(l, ..., T)$\\

$j \neq l'$, $j' \neq l \Rightarrow a(j, ...,l) \geq a_{jj'} + a_{l'l}$\\
\tab \tab \tab \tab $a(s, ..., j) \geq U_j^F \tab \Rightarrow a(P_{st}) \geq U_j^F + a_{jj'}+a_{l'l}+U_l^B$\\
\tab \tab \tab \tab $a(j, ..., l) \geq U_l^B$\\


\newpage
\textbf{c.}
Atribuirea valorii $before[j]$ se face în blocul $if(u_j^F > u_{j*}^F + a_{j*j})$ în care se intră doar dacă $a_{j*j}$ este finit. Avem astfel $j, before[j]$ vecini $\forall j$. Analog $j, after[j]$ vecini. \\

$\forall j U_j^B \neq \infty \iff \exists k \in T$ astfel încât $\{k,j\} \in E$ \\

$\forall j U_j^B \neq \infty \iff \exists k \in T$ astfel încât $\{k,j\} \in E$ \\\\
$U\neq\infty \iff U_{j*}^F, a_{j*j}, U_j^B \neq \infty \tab sau \tab u_l^F, a_{ll*}, u_l^B \neq \infty$\\
$\iff \exists$ 2 noduri vecine, unul în $S$ si unul în $T$ $\Rightarrow P_0 = s, ..., before(i), i, after(i), ..., t$ drum. \\
În blocul $for(j\in V-S)$ se calculează drumul minim de la $S$ la oricare dintre nodurile ce au fost adăugate în $S$ (e algoritmul lui Dijkstra până la un anumit pas). La fel în blocul $for(l\in V-T)$ drumul minim de la $t$ la orice nod din $T$.\\
$a(P_0) = u_j^F + a_{jl} + u_l^B = U$ returnat de algoritm.\\
\tab Fie P un drum de la $s$ la $t$.\\
\tab \textbf{I.}
$P \subseteq S \cup T$. \\
Procedând ca la \textbf{b.} obținem $a(P) \geq U_j^f + a_{jl} + U_l^B = U = a(P_0)$.\\
\tab \textbf{II.}
Presupunem prin reducere la absurd că $a(P) < U,  N \in P, N \notin S \cup T$.\\

\tab $U_N^F > min_{j \in V-S}u_j^F;\tab U_n^B > min_{l\in V-T};\tab U_N^F + U_N^B \leq a(P) < U$\\

$\Rightarrow min_{j\in V-S} U_j^F + min_{l\in V-T} U_l^B < U$\\
$\Rightarrow$ algoritmul nu va ieși din while, deci presupunerea este falsă.\\
$\Rightarrow a(P) \geq a(P_0) \forall P \Rightarrow P_0$ drum de cost minim.\\