Oque isso esta querendo dizer?

[Vigaku 0]

Implementação básica do algoritmo de Djikstra.

 

void DIGRAPHsptD1(Digraph G, Vertex s, Vertex parnt[], double cst[]){

Vertex w, w0, fr[maxV];

for (w = 0; w < G->V; w++) {

parnt[w] = -1;

cst[w] = maxCST;

}

fr = s;

cst = 0.0;

while (1) {

double mincst = maxCST;

for (w = 0; w < G->V; w++) {

if (parnt[w] == -1 && mincst > cst[w])

mincst = cst[w0=w];

if (mincst == maxCST) break;

parnt[w0] = fr[w0];

for (w = 0; w < G->V; w++)

if (cst[w] > cst[w0] + G->adj[w0][w]) {

cst[w] = cst[w0] + G->adj[w0][w];

fr[w] = w0;

}

}

}

 

Galera, to precisando urgente de uma ajuda, keria saber oa esta havendo nesse código, é um lance de nós com ponteiro. Por favor algume me da um help, é urgente :(

[_Isis_ 202]

O algoritmo de Dijkstra procura o menor caminho num grafo com arestas de peso não-negativo.

 

http://www.ime.usp.br/~pf/algoritmos_para_...s/dijkstra.html

[Vigaku 0]

Oi Izis,

Isso eu sei.... o problema q ai nesse código esta acontecendo algo, um fulando apontando para o nó X e X recebendo alguma coisa e assim vai....

Essa aula eu perdi, preciso urgente disso......

 

tkx Izis http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[_Isis_ 202]

O problema desse código é que falta coisa:

 

- Fechar as chaves do primeiro for.

- w0 é inicializado com o quê?

 

Tudo começa com maxCST e -1 em cst, sendo mincst = maxCST, então o primeiro if do 1º não é executado nunca e o resto das operações com array tem índice indefinido.

[Vigaku 0]

Sim o codigo esta imcompleto mesmo..... é apenas um trexo, mas tenho q saber sobre este trexo.

E de errado ele não tem nada, foi o Prof. q passou ele. N fui na aula desse dia, me ferrei :(

[_Isis_ 202]

Certeza que não tem nada de errado?

 

void DIGRAPHsptD1(Digraph G, Vertex s, Vertex parnt[], double cst[]){
  Vertex w, w0, fr[maxV];
  for (w = 0; w < G->V; w++) {
	parnt[w] = -1;
	cst[w] = maxCST;
  } // FIM DO FOR DE INICIALIZAÇÃO

  fr[s] = s;
  cst[s] = 0.0;

  while (1) {
	double mincst = maxCST;
	for (w = 0; w < G->V; w++) {
		  if (parnt[w] == -1 && mincst > cst[w])
				  mincst = cst[w0=w];
		  if (mincst == maxCST)
				   break;
		  parnt[w0] = fr[w0];
		  for (w = 0; w < G->V; w++)
				 if (cst[w] > cst[w0] + G->adj[w0][w]) {
							 cst[w] = cst[w0] + G->adj[w0][w];
							 fr[w] = w0;
				 } // FIM DO IF DA RELAXACAO
	} // FIM DO FOR OU DO WHILE??
} // FIM DO WHILE OU DA FUNCAO??

 

Se você tem 4 vértices no grafo:

parnt: -1 -1 -1 -1

cst: * * * *

fr: ? ? ? ?

 

 

S = 2

parnt: -1 -1 -1 -1

cst: * * 0.0 *

fr : ? ? 2 ?

 

-> while(1)

-> double mincst = *

-> w = 0

-> if (parnt[0] == -1 && mincst > cst[0]): FALSO

-> if (mincst == maxCST) : VERDADEIRO. Sai do loop for e vai para o while(1)

 

Ou então se a chave vier logo após o break:

 

-> while(1)

-> mincst = *

-> w = 0

-> if (parnt[0] == -1 && mincst > cst[0]): FALSO

-> if (mincst == maxCST) : VERDADEIRO. Sai do loop for e segue.

-> parnt[w0] = fr[w0] : w0 não foi definido. Coisas erradas acontecem aqui.

 

Pelo jeito da coisa isso deve ser C ou C++ sem classes.