Algoritmia - Ayuda Dijsktra

 
Vista:

Ayuda Dijsktra

Publicado por marisa (1 intervención) el 18/11/2005 12:13:19
Necesito ayuda urgente por favor, si alguien tiene el algoritmo de dijkstra en pascal o en c y me lo puede mandar se lo agradeceria un monton, mi correo es marisalopez2006@yahoo.es
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:Ayuda Dijsktra

Publicado por juan pedro (2 intervenciones) el 22/11/2005 19:13:44
se mas clara dijktra tiene como varios algoritmos
de q quieres seccion critica o exclusion mutua??
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Ayuda Dijsktra

Publicado por marisa (2 intervenciones) el 23/11/2005 20:08:54
Es el algoritmo de Dijsktra del camino mas corto
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Ayuda Dijsktra

Publicado por marisa (2 intervenciones) el 03/02/2006 17:09:56
Hola Disculpa pero tambien me estan dando esa clase y necesito hacer un proyecto con ese codigo, te agradeceria mucho si me lo puedes enviar a mi correo, churros_peka@hotmail.com, gracias de antemano, chau
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Ayuda Dijsktra

Publicado por Mauricio Armando (1 intervención) el 26/11/2005 03:52:44
espero te la rifes programando por que pues... no jala corrigelo y si le corriges las fallas me lo mandas no??? gracias... bye


#define INFINITY (MAX_INT - 1)

typedef struct {
int weight;
int dest;
} DijkEdge;

typedef struct {
DijkEdge* connections; /* Un array de arcos */
int numconnect;
int distance;
int isDead;
} Vertex;

void Dijkstra(Vertex* graph, int nodecount, int source) {
for(int i = 0; i < nodecount; i++) {
if(i == source) {
graph[i].distance = 0;
graph[i].isDead = 0;
} else {
graph[i].distance = INFINITY;
graph[i].isDead = 0;
}
}
for(int i = 0; i < nodecount; i++) {
int next;
int min = INFINITY+1;
for(int j = 0; j < nodecount; j++) {
if(!graph[j].isDead && graph[j].distance < min) {
next = j;
min = graph[j].distance;
}
}
for(int j = 0; j < graph[next].numconnect; j++) {
if(graph[graph[next].connections[j].dest].distance >
graph[next].distance + graph[next].connections[j].weight)
{
graph[graph[next].connections[j].dest].distance =
graph[next].distance + graph[next].connections[j].weight;
}
}
graph[next].isDead = 1;
}
for(int i = 0; i < nodecount; i++) {
printf(\"The distance between nodes %i and %i is %i\",
source, i, graph[i].distance);
}
}
/*
* Sea G=(V,A) un grafo dirigido y etiquetado.
* Sean los vértices a ∈ V y z ∈ V; a es el vértice de origen y z el vértice de destino.
* Sea un conjunto C ⊂ V, que contiene los vértices de V cuyo camino más corto desde a todavía no se conoce.
* Sea un vector D, con tantas dimensiones como elementos tiene V, y que “guarda” las distancias entre a y cada uno de los vértices de V.
* Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que conserva la información sobre qué vértice precede a cada uno de los vértices en el camino.

El algoritmo para determinar el camino de longitud mínima entre los vértices a y z es:

1. C ← V
2. Para todo vértice i ∈ C, i ≠ a, se establece Di ← ∞ ; Da ← 0
3. Para todo vértice i ∈ C se establece Pi = a
4. Se obtiene el vértice s ∈ C tal que no existe otro vértice w ∈ C tal que Dw < Ds
* Si s = z entonces se ha terminado el algoritmo.
5. Se elimina de C el vértice s: C ← C−{s}
6. Para cada arista e ∈ A de longitud l, que une el vértice s con algún otro vértice t ∈ C,
* Si l+Ds < Dt, entonces:
1. Se establece Dt ← l+Ds
2. Se establece Pt ← s
7. Se regresa al paso 4

Al terminar este algoritmo, en Dz estará guardada la distancia mínima entre a y z. Por otro lado, mediante el vector P se puede obtener el camino mínimo: en Pz estará y, el vértice que precede a z en el camino mínimo; en Py estará el que precede a y, y así sucesivamente, hasta llegar a a.
*/
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:Ayuda Dijsktra

Publicado por eui (1 intervención) el 01/02/2006 19:29:56
El siguiente algoritmo devuelve en una tabla de costes todos los caminos mínimos de
un nodo (el posición 1) a todos los demás

PROCEDURE Disjktra (G: TGrafo; VAR CosteMin: TCostes);
VAR
V : TConjunto;
I, J, X : Vertice;
BEGIN (*El vertice inicial se supone el 1*)
Incluir(V,1);
CosteMin[1]:= 0;
FOR I:= 2 TO N DO
CosteMin[I]:= G[1,I];
FOR I:=2 TO N DO
BEGIN
Escoger(X);
Incluir(V, X);
FOR J:= Todos los vertices no incluidos en U DO
IF CosteMin[X] + G[X,J] < CosteMin[J]
THEN CosteMin[J] := CosteMin[X] + G[X,J]
END;

La función escoger selecciona el vértice cuyo costemin[X] sea el mas pequeño y que
esté fuera de V*)
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar