Grafo

uni
Un Grafo $G=(V,E)$ consiste in:

• un insieme $V$ di vertici (o nodi).
• un insieme $E$ di coppie di vertici, detti archi.
  Ogni arco connette due vertici
  Un grafo Orientato (o diretto) è un grafo di archi orientati e rappresenta relazioni orientate tra coppie di oggetti.
  Un grafo non orientato (o non diretto) è un grafo di archi non orientati e rappresenta relazioni simmetriche tra coppie di oggetti.
  Un grafo non orientato si dice connesso se esiste un cammino tra ogni coppia di vertici.
  Un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino.

Cammino e Ciclo

Un cammino di un grafo $G=(V,E)$ da un vertice $x$ ad $y$ è dato da una sequenza di vertici $v_i$ di $V$ con $v_0=x$ e $v_k=y$, tale che per ogni $1\le i\le k$, l’arco $(v_{i-1},v_i)\in E$
Un cammino $(v_0,...,v_k)$ tale che $v_0=v_k$ è detto ciclo (va evitato).
Un grafo diretto è detto aciclico se non contiene cicli.
Un cammino è quindi il numero di nodi che crea un arco tra due nodi di partenza ed arrivo.

Cammino Minimo

Il cammino minimo è quel cammino che permette di attraversare il minimo numero di nodi.

Algoritmi di ricerca del Cammino Minimo

Algoritmo di Dijkstra

Si applica ai grafi orientati che hanno peso positivo sugli archi.
Trova i cammini minimi da un nodo di partenza a tutti gli altri nodi.
Questo è un algoritmo greedy, prende decisioni locali sperando che siano le scelte migliori globalmente.
I cammini minimi vengono inizialmente posti ad infinito e vengono via via aggiornati con stime sempre piè precise ad ogni iterazione di un ciclo, quando un nuovo nodo viene “sistemato” quindi stabilizza il cammino.
Utilizza due tabelle dist e pred con $n$ elementi ($n$ = numero di nodi).