[C] Implementazione algoritmo di Dijkstra

[gila75]

Ciao a tutti, sto studiando l'algoritmo di Dijkstra e ho provato ad implementarlo.
Codice:

Codice: Seleziona tutto

/// gcc -Wall -g 3d.c -o xx 

#include <stdio.h>
#include <stdlib.h>
#define N 6
#define INF 10000
#define ASCII 97

void init_distanze(int distanze[N]);
void azzera_nodo(int grafo[N][N],int start);
int cerca_minimi(int distanze[N],int grafo[N][N],int start);
//-----------------------------------------------------------------------------------------------------
// cerca nodo con distanza minima
// nodo contrassegnato con -2 anche se presenta distanza minima
// non può essere usato perchè già stato usato

int cerca_minimi(int distanze[N],int grafo[N][N],int start)
{
	int min,tmp,tmp2, i;
	
	for (i=1; i<N; i++)
	{
		if (distanze[i]<INF && grafo[i][i]!=-2 )
		{
			tmp=distanze[i];
			tmp2=i;
			min=tmp;
			break;
		}
	}
	
	for (i=1; i<N; i++)
	{
		if ( (distanze[i]<tmp) && grafo[i][i]!=-2 )
		{
			tmp=distanze[i];
			if (tmp<min)  
			{
				min=tmp;
				tmp2=i;
			}
		}
	}
	return tmp2;
}
	
//-----------------------------------------------------------------------------------------------------	
// il nodo di partenza ha già visitato altri nodi,quindi va scartato
// e non deve più essere considerato

void azzera_nodo(int grafo[N][N],int start)
{
	int i;
	for (i=0; i<N; i++)
		grafo[i][start]=-1;
	grafo[start][start]=-2;
}
//-----------------------------------------------------------------------------------------------------
// inizializzazione distanze: tutti i nodi tranne il primo hanno
// distanza infinita. Io li imposto a 10000 perchè non so gestire infinito in C
// nodo zero impostato a zero

void init_distanze(int distanze[N])
{
	int i;
	for (i=0; i<N; i++)
		distanze[i]=INF;
	distanze[0]=0;
}
//-----------------------------------------------------------------------------------------------------	


int main(void) {
  	int grafo[N][N]={{-1,5,6,1,-1,-1},
  					{5,-1,-1,1,1,7 },
  					{6,-1,-1,-1,1,1},
  					{1,1,-1,-1,3,-1},
  					{-1,1,1,3,-1,3 },
  					{-1,7,1,-1,3,-1}};
	int distanze[N];
	int nodi_precedenti[N]={0};
  	int i,k,temp,min;
  	int start=0;
  	int z=0;
  	char s[20];
  	
  	init_distanze(distanze);
  	for (i=0; i<N-1; i++) // scansiona per N-1 volte i nodi
  	{
  		for (k=0; k<N; k++)
  		{
  			if (grafo[start][k]>=0) // scansiona nodo per vedere a cosa è connesso
  			{
  				temp=distanze[start]+grafo[start][k];
  				if (temp<distanze[k])
  				{
  					distanze[k]=temp;
  					nodi_precedenti[k]=start;	
  				}
  			}
  		}
  		
  		azzera_nodo(grafo,start);
  		min=cerca_minimi(distanze,grafo,start);
  		start=min;
  	}
//-----------------------------------------------------------------------------------------------------
// stampo percorso partendo da nodo 0 (o nodo A)

  	s[z]=(N-1)+ASCII;
 	for (i=N-1; i!=nodi_precedenti[i]; i=nodi_precedenti[i])
 	{
 		z++;
 		s[z]=nodi_precedenti[i]+ASCII;
 	}
 		
 	for (i=z; i>=0; i--)
 		printf ("%c",s[i]);
 	puts("");
  
return 0;
}

qualche domanda:
1) Il grafo deve essere orientato? Alcuni articoli dicono di si, altri no. A parte che può essere "misto", cioè alcuni archi orientati e altri no.
per esempio un senso unico in un percorso deve per forza essere orientato.

2) io ho implementato il grafo con una matrice di adiacenze, ma se per piccoli grafi va bene, salendo di numero diventa un problema di
memoria essendo pari a NODI*NODI. Cosa potrebbe essere un alternativa ? Le liste. Ci avevo pensato, ma a conti fatti, visto che devi scomodare l'allocazione dinamica non so fino a che punto il gioco valga la candela.
Oltretutto le liste le devi scorrere tutte, non come gli array che hanno indici. Logicamente non c'è un meglio, va valutato caso per caso, ma mi piacerebbe avere consigli.

3) mi pare di aver letto che nell'algoritmo di Dijkstra si usa anche una coda di priorità (che al momento non so bene padroneggiare), ma non so a che scopo.

4) come posso gestire il concetto infinito in C? c'e' qualche scappatoia?

Comunque il codice (a meno di sviste e bug sfuggiti) funziona.
Se qualcuno mi desse info aggiuntive, io sono qui, grazie.

[DoctorStrange]

Non mi esprimo sul codice, perché di C non mi intendo.
Per quanto riguarda le domande:
1) L'enunciato originale dell'algoritmo non richiede formalmente che i segmenti d'arco siano orientati, questo perché deve potersi adattare al caso più generalista possibile. Se, comunque gli archi sono orientati, allora il grafo ha un limite imposto che ridurrà in maniera consistente le iterazioni necessarie per arrivare all'ordinamento finale e quindi ad estrarre il percorso minimo. Diciamo che il grafo con gli archi orientati è un sottoinsieme più restrittivo del caso generico.
2)Quale che sia la collection che tu voglia usare, che sia lista, vector, array, o come si chiamano gli equivalenti in C, tendenzialmente appare logico che, all'aumentare delle dimensioni del grafo o, meglio, del numero di nodi in un grafo, le iterazioni necessarie aumenteranno esponenzialmente. L'idea di massima è che questo è un algoritmo iteratoivo e quindi, come tale dovresti considerarlo. Per ogni coppia di nodi, creerai una variabile di appoggio nella quale metterai, di volta in volta il cammino scelto ed il suo peso. Una volta che avrai trovato il cammino ottimo, cioè quello con il peso minore, allora scarterai tutti i parziali precedenti. Se l'algoritmo iterativo sarà fatto bene, avrai un'allocazione di memoria ingente durante l'esecuzione, ma poi si ridurrà usando le funzioni ricorsiive.
3)Non saprei
4)infinito? Hai a disposizione una certa quantità di memoria, e quella è. Inoltre sarebbe utile che tu implementassi un meccanismo che controlli che l'allocazioone non cresca oltre un certo limite. Se la richiesta di memoria dovesse crescere oltre un limite massimo, manderai un messaggio all'utente, che ha superato il valore massimo consentito.

[Actarus5]

2) Purtroppo per le matrici di adiacenza la memoria occupata è Ω(|V|^2), dove V è il numero di vertici, mentre per le liste di adiacenza è Ω(|V| + |E|). Va da sé che la seconda è estremamente conveniente quando hai a che fare con dei grafi "sparsi". Onestamente continuerei con le matrici di adiacenza a meno che la memoria non sia davvero un problema, poi per carità come esperimento puoi provare entrambe le rappresentazioni, diciamo che la seconda è più complessa da usare.

3) È vero, dai miei appunti in pseudo-codice:

Codice: Seleziona tutto

function Dijkstra(Graph, source):
    for each vertex v in Graph.Vertices:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q
    dist[source] ← 0

    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q

        for each neighbor v of u still in Q:
            alt ← dist[u] + Graph.Edges(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

dove:

Codice: Seleziona tutto

dist è un array che contiene le distanze attuali dalla sorgente agli altri vertici, ad esempio, "dist[u]" è la distanza attuale dalla sorgente al vertice u.
prev è un array che contiene i puntatori ai nodi del salto precedente sul percorso più breve dalla sorgente al dato vertice.
Graph.Edges(u, v) restituisce la lunghezza dell'arco che collega i nodi u e v.
alt è la lunghezza del percorso dal nodo radice al nodo vicino v se si passa attraverso u.

La coda di priorità ti serve ad estrarre "prima possibile" il nodo con distanza minima dalla sorgente, aka: il nodo col valore "dist[u]" più piccolo. Ogni volta che cambia la distanza di un nodo con la coda di priorità aggiorni la posizione dei nodi, per tenere "accessibile" il nodo più vicino. 

4) Cosa intendi col concetto di infinito? Dici per la distanza all'inizio quando implementi l'algoritmo? Dipende dal grafo, per numeri ragionevolmente umani usare INT_MAX va benissimo, insomma una costante molto grande a piacere, un po' come hai fatto tu.

[gila75]

Grazie per le risposte. Sono sul traghetto per le vacanze. Analizzo e rispondo bene appena rientro.
Immaginavo che la coda di priorità servisse per quello. Non so bene cosa siano, so cosa è una coda, ma coda di priorità ( è vero che lo dice la parola), non molto.
Intanto grazie

[gila75]

Eccomi di ritorno.

La coda di priorità ti serve ad estrarre "prima possibile" il nodo con distanza minima dalla sorgente, aka: il nodo col valore "dist u" più piccolo. Ogni volta che cambia la distanza di un nodo con la coda di priorità aggiorni la posizione dei nodi, per tenere "accessibile" il nodo più vicino.

Si, immaginavo, la distanza minima ha priorità, e non si deve scorrere ogni volta per cercare il minimo. Su array piccoli poco importa,
ma su grandi dimensioni credo sia importante.
Però credo che serva anche tener traccia a quale nodo fa riferimento la distanza minima che ora si è messa in priorità.

Proverò a cercare come s'implementa una coda con priorità.

Onestamente continuerei con le matrici di adiacenza a meno che la memoria non sia davvero un problema, poi per carità come esperimento puoi provare entrambe le rappresentazioni, diciamo che la seconda è più complessa da usare.

Si, sarei curioso di provare, ma non so bene come funziona. Una lista che si deve dividere in più percorsi per seguire più nodi.
Cerco anche questo.
Il mio programma era una prova, ho cercato di risparmiare un array , quello che tiene traccia dei nodi già visitati, marcando la matrice
in un determinato punto con -2 e sembra funzionare.
Comunque, grazie a tutti e due per i consigli. Se avete stralci di codice o info per coda con priorità e grafi fatti con liste, io sono qui.
Intanto cerco anche io su libri e web