e-commerce84
01-07-2012, 13:22
Probabilmente è una domanda stupiderrima ma sono nelle giornate pre esame e stò andando nel panico e mi vengono dubbi sulle cose più stupide...
Allora io ho un grafo G = (V, E, w) NON DIRETTO e PESATO
Se devo calcolare l'albero dei cammini minimi da un nodo s verso tutti gli altri nodi NON POSSO USARE l'algoritmo shortestPath che fà uso della visita per ampiezza (perchè quello và bene per grafi non pesati o per meglio dire per grafi con archi tutti di peso unitario...) ma posso usare o l'algoritmo di Dijkstra o l'algoritmo di Bellman Ford o l'algoritmo di Floyd-Roy-Warshal (nel caso in cui volessi risolvere il problema dell'All Pairs Shortest Path, quindi nel caso in cui volessi calcolare un cammino minimo che collega ogni coppia di nodi)
Giusto? Questi algoritmi io li ho sempre usati sui grafi diretti, in questo caso però il grafo è NON DIRETTO ma credo che funzionino lo stesso considerando l'osservazione che se prendo 2 nodi A e B si ha che P(A,B) == P(B,A), quindi basta che ne calcolo uno dei 2 ed ho pure l'altro...in pratica è come se dovessi calcolare solo metà dei cammini minimi
Va bene come ragionamento?
Grazie
Andrea
Allora io ho un grafo G = (V, E, w) NON DIRETTO e PESATO
Se devo calcolare l'albero dei cammini minimi da un nodo s verso tutti gli altri nodi NON POSSO USARE l'algoritmo shortestPath che fà uso della visita per ampiezza (perchè quello và bene per grafi non pesati o per meglio dire per grafi con archi tutti di peso unitario...) ma posso usare o l'algoritmo di Dijkstra o l'algoritmo di Bellman Ford o l'algoritmo di Floyd-Roy-Warshal (nel caso in cui volessi risolvere il problema dell'All Pairs Shortest Path, quindi nel caso in cui volessi calcolare un cammino minimo che collega ogni coppia di nodi)
Giusto? Questi algoritmi io li ho sempre usati sui grafi diretti, in questo caso però il grafo è NON DIRETTO ma credo che funzionino lo stesso considerando l'osservazione che se prendo 2 nodi A e B si ha che P(A,B) == P(B,A), quindi basta che ne calcolo uno dei 2 ed ho pure l'altro...in pratica è come se dovessi calcolare solo metà dei cammini minimi
Va bene come ragionamento?
Grazie
Andrea