Grafi - Cammini minimi - Definizione generale

[mrpoint]

ditemi se le seguenti affermazioni sono corrette ed eventualmente se c'è qualcosa da aggiungere, grazie mille in anticipo;

Sia $G:=(V,A)$ il grafo con V definito come l'insieme dei nodi e A l'insieme degli Archi; $AAa_(ij) in A$ associo un costo $c(a)$.
Definisco la variabile $x_(ij) in ZZ_+$ allora

$min sum c_(ij) * x_(ij)$



In soldoni:

Definisco un grafo G composto da V vertici e A archi, definisco una variabile intera positiva x che indica quante volte prendo l'arco nella mia soluzione finale (con relativo costo associato) e minimizzo il costo dalla sorgente per ogni nodo.

[codino75]

puoi essere piu' esplicito sul tuo quesito?
non ho ben capito se vuoi enunciare un algoritmo, la definizione di grafo o che cosa.
ciao alessandro?

[_luca.barletta]

"mrpoint":ditemi se le seguenti affermazioni sono corrette ed eventualmente se c'è qualcosa da aggiungere, grazie mille in anticipo;

Sia $G:=(V,A)$ il grafo con V definito come l'insieme dei nodi e A l'insieme degli Archi; $AAa_(ij) in A$ associo un costo $c(a)$.
Definisco la variabile $x_(ij) in ZZ_+$ allora

$min sum c_(ij) * x_(ij)$

Diciamo che questo è il punto di partenza, ora ti mancano tutti i vincoli da impostare.

[mrpoint]

Si capisco che possa sembrare strano che uno cerchi conferme su di una definizione così generale. Volevo solo comunque sapere se era formalmente giusto definire un cammino minimo in quel modo. Grazie a tutti

[_luca.barletta]

Quella che hai indicato è solo una funzione obiettivo; se vuoi proprio definire un cammino su G devi aggiungere dei vincoli, ad esempio il grado di ogni nodo.

[codino75]

un insieme di archi non e' in generale un cammino

[mrpoint]

Scusatemi ma

$min sum c_(ij)⋅x_(ij)$

questo non è un vincolo? voglio dire, si dice espressamente che la somma dei costi debba essere minima rispetto ogni nodo.

[_luca.barletta]

ma devi anche descrivere come prendi i nodi

quello non è un vincolo, ma una funzione di costo