Sia $G=(N,A)$ un grafo orientato su cui sia definito un vettore $\underline{c} = [c_{ij}]$ dei costi associati agli archi del grafo
Inoltre, siano $s$ e $t$ due nodi distinti, detti rispettivamente origine e destinazione
Il problema dei cammini minimi uno a uno consiste nel determinare il percorso di costo minimo (più corto) da $s$ a $t$
$c_{ij} =$ costo dell’arco $(i,j)$
$x_{ij} =$ variabili decisionali
$x_{ij} = \begin{cases} 1 \space\space \space \space \text{ se } x_{ij} \in p \\0 \space\space \space \space \text{ se } x_{ij} \notin p \end{cases}$
$min \sum_{(i,j) \in A} c_{ij} x_{ij}$
$\sum_{j \in FS(i)} x_{ij} - \sum_{j \in BS(i) } x_{ji} = \begin{cases} 1 \space\space \space \space \text{ se } i = s \\ 0 \space\space \space \space \text{ se } i \in N \backslash \{s,t\} \\ -1 \space\space \space \space \text{ se } i = t \end{cases}$
$x_{ij} \in \{0,1\}$
Sia $G= (N,A)$ un grafo orientato su cui sia definito un vettore $\underline{c} = [c_{ij}]$ dei costi associati agli archi del grafo
Inoltre, sia $s$ il nodo di origine
Il problema dei cammini minimi uno a tutti consiste nel determinare l’albero dei cammini minimi da $s$ a tutti gli altri nodi di $G$