2023-12-19 - label correcting

universityin-classsubject-2101

2023-12-19 - label correcting

Algoritmi

Algoritmo di Dijkstra

L’insieme è diviso in due sottoinsiemi: e :

• contiene i nodi che sono portati a convergenza.
• In sono presenti sia i nodi non portati a convergenza (), sia quelli portati a convergenza ancora da individuare ()

L’algoritmo si basa sul’assunzione che, in seguito a tutti i rilassamenti a partire da un nodo portato a convergenza, in sia presente almeno un elemento portato a convergenza, e quest’ultimo coincide con il nodo per cui è minimo in .
Se esistessero archi con peso negativo questa assunzione sarebbe sbagliata.

Avendo la necessità di prendere il nodo con minimo, si presta bene l’implementazione di con una coda con priorità Min-Heap.

nel codice l’insieme non esiste, perché non serve salvare gli elementi. Vengono utilizzati soltanto quando vengono spostati e nel codice coincidono con la variabile u

DIJKSTRA (G, w, s):
	FOR v IN G.V:                 O(V)
		d[v] = +INF
		PI[v] = NULL
	d[s] = 0
	Q = BuildMinHeap(G.V)         O(V)
	FOR i=1 TO |G.V|:             O(V)
		u = extractMin(Q)         O(log V)
		FOR v IN G.Adj(u):        O(E)
			RELAX(u, v, w)        O(log V)

La complessità è .

Complessità Algoritmi Label Correcting

Algoritmo	Liste	Matrici
Dijkstra	O((V+E) * logV)	O(V^2 * log V)
Bellman-Ford	O(VE)	O(V^3)
Dag-SP	O(V+E)	O(V^2)

Componenti Connesse

Sono dei sottografi per cui esiste un cammino da ogni nodo verso tutti gli altri (e quindi sono necessari cicli).

Si consideri un grafo formato da componenti connesse. Non possono esistere cicli da una componente all’altra.
Se esistesse, le due componenti connesse sarebbero da considerarsi come un’unica.