Jump to content
Miketo

Segmentation fault :o

Recommended Posts

Miketo

Bom dia.

Trago aqui uma dúvida que por mais que procure, ainda não consegui explicar o porquê, e talvez algum de vós me saiba dar a resposta.

A minha idéia é fazer uma representação de uma rede com listas de adjacência. Até aqui tudo bem. Depois de ter a representação feita, fiz um algoritmo de Dijkstra para o cálculo do caminho mais curto de um nó até todos os outros nós da rede. E agora que vem o problema. Eu quero que, após seja criada a rede e apresentada a sua representação, seja dada a possibilidade de se escolher qual o nó de origem do cálculo. O problema, é que no momento em que deveria ser indicado o nó, ou seja, na linha de código

cin >> no;

o programa pára e dá um erro 139, ou seja, segmentation fault. O problema, é que se meter o cin antes de ser criada a rede e ser apresentada, o programa não dá qualquer erro, e calcula os custos dos caminhos bem. Para que melhor percebam o que estou a tentar fazer, vou colocar aqui o código que fiz. Se souberem o que causa o mal, por favor ajudem-me.

O ficheiro de leitura é um simples txt que deve conter a informação dos nós e o seu custo, algo deste género:

1 2 4

1 3 2

2 3 1

#include <iostream>
#include <iomanip>
#include <fstream>
#include <map>
#include <queue>	// para priority queue
#include <limits.h>	// inclui valor de infinito

using namespace std;

#define pii pair< int, int >	// par inteiro-inteiro
#define INF INT_MAX				// define INF como o maior numero inteiro possivel


class Grafo{

public:
	struct ListNode{
		int nome;				// nó adjacente
		int custo;				// custo da ligação do nó cauda ao nó adjacente
		struct ListNode *next;	// ponteiro para proximo nó adjacente.
	};

	map<int, struct ListNode*> nodes; 	// mapeamento dos nós adjacentes da rede

	ListNode *head;				// ponteiro para inicio da lista de adjacencia


	Grafo(){ 					// Construtor
		head = NULL;	 		// inicializacao da lista vazia
	}

	// Faz comparação
	struct comp {
		bool operator() (const pii &a, const pii &b) {
			return a.second > b.second;
		}
	};

	// fila que vai armazenar pares arco-custo
	priority_queue< pii, vector< pii >, comp > Q;	// fila Q que vai receber o par arco-custo

	void Cria_Rede();				// funcao que cria a rede
	void MostraNosAdjacentes();		// mostra a lista de nos adjacentes da rede
	int Pergunta();					// pergunta nó origem de Dijkstra
	void Dijkstra(int noorig);		// calcula o caminho mais curto de um no a escolha para todos os outro

};

void Grafo :: Cria_Rede() {

int u, v, w, u2, v2, w2;

ListNode *NoAdj;  	// Novo no da rede
ListNode *nodePtr;	//

freopen("rede.txt","r", stdin);

while(!feof(stdin)){
	scanf("%d %d %d", &u, &v, &w);
	if(u!=u2 || v!=v2 || w!=w2){	// impede repetição de arcos
		u2=u;	v2=v;	w2=w;
		cout << u << " - " << v << " - " << w << endl;

		/*
		Como os ramos são bidireccionais, vai criar dois ramos
		unidireccionais com o mesmo custo, entre os nós em questão
		*/

		// insere ramo no nó u
		NoAdj = new ListNode;
		NoAdj->nome = v;
		NoAdj->custo = w;
		NoAdj->next = NULL;

		if(nodes.count(u)==0){	// nó ainda não está definido
			nodes.insert(pair<int, struct ListNode*>(u, NoAdj));
		}
		else{
			nodePtr = nodes[u];
			while(nodePtr->next){	// corre a lista até ao último elemento
				nodePtr = nodePtr->next;
			}	
			nodePtr->next = NoAdj;	// coloca ponteiro do ultimo elemento da lista a apontar para o novo no
		}

		// insere ramo no nó v
		NoAdj = new ListNode;
		NoAdj->nome = u;
		NoAdj->custo = w;
		NoAdj->next = NULL;

		if(nodes.count(v)==0){	// nó ainda não está definido
			nodes.insert(pair<int, struct ListNode*>(v, NoAdj));
		}
		else{
			nodePtr = nodes[v];
			while(nodePtr->next){	// corre a lista até ao último elemento
				nodePtr = nodePtr->next;
			}	
			nodePtr->next = NoAdj;	//	coloca ponteiro do ultimo elemento da lista a apontar para o novo no
		}
	}		
}
fclose (stdin);	// fecha ficheiro
}

void Grafo :: MostraNosAdjacentes(){
map<int, struct ListNode*>::iterator itr;

ListNode *nodePtr; // Ponteiro que percorre a lista

cout << endl << "Lista de Adjacencia da rede:" << endl;
for(itr = nodes.begin(); itr != nodes.end(); itr++){ 
	cout << itr->first <<" --> ";

	nodePtr = itr->second; // define o inicio da lista

	while(nodePtr){  // passa por todos os nos da lista, até chegar ao fim desta

		cout << nodePtr->nome << "[" << nodePtr->custo << "] ->";
		nodePtr = nodePtr->next;	// passa o ponteiro para o proximo no da lista
	}
	cout << "NULL" << endl;	// indica o fim da lista
}
}

int Grafo :: Pergunta(){

int no;

cout << endl << "indique o no de origem:";
cin >> no;

return no;
}


void Grafo :: Dijkstra(int noorig){

int Vo;				// nó origem
int numnosrede;		// número de nós da rede
int i, u, v, w, sz;	// variáveis auxiliares

ListNode *nodePtr; // Ponteiro que percorre a lista de adjacencia

numnosrede = (int) nodes.size();	// devolve número de nós da rede

int D[numnosrede];	// vector que vai receber valor das distâncias

// vector G (3D) de pares int-int
vector< pii > G[numnosrede];

// Vector F booleano para controlo de etiquetagem
bool F[numnosrede];
for(int i=0; i<numnosrede; i++){
	F[i]=0;	// nenhum nó está etiquetado!
}

Vo=noorig;

// inicialização do grafo
   for(i=0; i<numnosrede; i++){
	D[i] = INF;		// distância para todos os nós inicializada como "infinita"
}

   D[Vo-1] = 0;			// Distância do nó inicial a si próprio é 0
   Q.push(pii(Vo-1, 0)); 	// Coloca distância a si próprio na Fila Q

// Criação de tabela de adjacencia-custo
for(i=0; i<numnosrede; i++){
	nodePtr=nodes[i+1];	// ponteiro para lista de adjacencia do nó desejado
	while(nodePtr){	
		G[i].push_back (pii((nodePtr->nome)-1, nodePtr->custo));	// coloca em G os pares nó-custo adjacentes ao nó desejado
		nodePtr = nodePtr->next;	// move ponteiro para proximo no adjacente
	}
}

// Algoritmo Dijkstra
   while(!Q.empty()) {
       u = Q.top().first;	// retira o nome do nó

       Q.pop();			// apaga par da fila Q

       if(F[u]) continue;	// caso F[u] TRUE, nó já está etiquetado, passa para próxima iteração

       sz = G[u].size();	// número de nós adjacentes a u

       for(i=0; i<sz; i++) {
           v = G[u][i].first;	// Nome do nó adjacente
           w = G[u][i].second;	// Custo da ligação

           if(!F[v] && D[u]+w < D[v]) {	// Se nó ainda não foi etiquetado e novo custo menor que custo actual
               D[v] = D[u] + w;			// Novo custo atribuído à ligação
               Q.push(pii(v, D[v]));		// Coloca par na fila Q
           }
       }
       F[u] = 1; // u está etiquetado
   }

// resultado
   cout << endl << "numero de nodos: " << numnosrede << endl;

   for(i=0; i<numnosrede; i++){
	cout << " Distancia mínima de " << Vo << " a " << i+1 << ":" << D[i] << endl;
}

}

int main(){

int no;
Grafo a;

no=a.Pergunta();	// aqui não dá erro!
a.Cria_Rede();
a.MostraNosAdjacentes();

//no=a.Pergunta();	// aqui dá erro!

a.Dijkstra(no);

return 0;
}

Share this post


Link to post
Share on other sites
daj

Provavelmente obténs esse erro porque andas a alterar o stdin no Cria_Grafo. Se queres ler o ficheiro com as funções de C, porque é que não usas o fopen e o fscanf em vez do freopen e do scanf?

Share this post


Link to post
Share on other sites
Miketo

Alterei?  :(

Pois, não tinha noção disso. Manipular ficheiros foi sempre coisa que não soube fazer bem. Como aconselhas então que faça a leitura? É que eu tentei com o fstream, mas leu-me o ficheiro todo de uma vez, e eu queria uma linha de cada vez, como tenho agora.

Share this post


Link to post
Share on other sites
Localhost

fclose (stdin); // fecha ficheiro

Esta linha está a causar o problema.

Tu devias receber com um file pointer o retorno da função freopen e depois trabalhares com o ponteiro em si.


here since 2009

Share this post


Link to post
Share on other sites
Miketo

Consegui!! :D :D

Segui o que o daj disse e já deu. Modifiquei a função Cria_Rede assim:

int u, v, w, u2, v2, w2;

ListNode *NoAdj;  	// Novo no da rede
ListNode *nodePtr;	//
FILE * fich;

fich= fopen("rede.txt","r");

while(!feof(fich)){
	fscanf(fich, "%d %d %d", &u, &v, &w);
	if(u!=u2 || v!=v2 || w!=w2){	// impede repetição de arcos
		u2=u;	v2=v;	w2=w;
		cout << u << " - " << v << " - " << w << endl;


		/* 
		Como os ramos são bidireccionais, vai criar dois ramos 
		unidireccionais com o mesmo custo, entre os nós em questão
		*/

		// insere ramo no nó u
		NoAdj = new ListNode;
		NoAdj->nome = v;
		NoAdj->custo = w;
		NoAdj->next = NULL;

		if(nodes.count(u)==0){	// nó ainda não está definido
			nodes.insert(pair<int, struct ListNode*>(u, NoAdj));
		}
		else{
			nodePtr = nodes[u];
			while(nodePtr->next){	// corre a lista até ao último elemento
				nodePtr = nodePtr->next;
			}	
			nodePtr->next = NoAdj;	// coloca ponteiro do ultimo elemento da lista a apontar para o novo no
		}

		// insere ramo no nó v
		NoAdj = new ListNode;
		NoAdj->nome = u;
		NoAdj->custo = w;
		NoAdj->next = NULL;

		if(nodes.count(v)==0){	// nó ainda não está definido
			nodes.insert(pair<int, struct ListNode*>(v, NoAdj));
		}
		else{
			nodePtr = nodes[v];
			while(nodePtr->next){	// corre a lista até ao último elemento
				nodePtr = nodePtr->next;
			}	
			nodePtr->next = NoAdj;	//	coloca ponteiro do ultimo elemento da lista a apontar para o novo no
		}
	}		
}
fclose (fich);	// fecha ficheiro

Já testei, e deixou de dar problema. Muito obrigado  :(

Share this post


Link to post
Share on other sites
Localhost

@Miketo: uma dica que não tem propriamente a ver com o teu problema. Por que é que não declaras um objecto da classe queue dentro da tua estrutura ListNode? Era muito mais fácil e não precisavas de andar a trabalhar com ponteiros. Vou-te deixar uma implementação minha do algoritmo de Dijkstra e diz-me se te agradam as diferenças:

#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

typedef struct 
{
    int cost, dest;
} Edges;

typedef struct
{
    int dist;
    bool used;
    queue<Edges> edges;
} Vertex;

int n = 0, v = 0, k = 0;
Vertex vertex[10000];

int find_min () 
{
    int minPos = 0, minVal = INT_MAX;
    
    for (int i = 0; i < k; i++) 
    {
        if (vertex[i].used == false) 
        {
            if (vertex[i].dist < minVal) 
            { 
	minVal = vertex[i].dist; 
	minPos = i; 
    }
        }
     }
    
    return minPos;
}

void dijkstra (int from, int to, int u) 
{
    int aux = k, minPos = 0;
    Edges head;
    
    for (int i = 0; i < 10000; i++) 
    { 
vertex[i].dist = INT_MAX; 
vertex[i].used = false; 
    }
    
    vertex[from].dist = 0;
    while (aux > 0) 
    {
        minPos = find_min ();
        vertex[minPos].used = true;
        
        while (!vertex[minPos].edges.empty ()) 
        {
            head = vertex[minPos].edges.front ();
            vertex[minPos].edges.pop ();
            if (vertex[minPos].dist + head.cost < vertex[head.dest].dist) 
                vertex[head.dest].dist = vertex[minPos].dist + head.cost;
        }
        aux--;
    }
    if (vertex[to].dist >= INT_MAX) printf ("NO\n");
    else printf ("%i\n",vertex[to].dist);
}

void input (int u) 
{
   int from = 0, to = 0;
   Edges novo;
    
    scanf ("%i %i",&v,&k);
    for (int i = 0; i < k; i++) 
    {
        scanf ("%i %i %i", &from, &novo.dest, &novo.cost);
        novo.dest--;
        vertex[from-1].edges.push (novo);
    }
    scanf ("%i %i", &from, &to);
    dijkstra (from-1,to-1,u);
}

int main () 
{
    scanf ("%i",&n);
    for (int i = 0; i < n; i++) input (i);
    
    return 0;
}

O contexto desta implementação está neste problema em específico: https://www.spoj.pl/problems/EZDIJKST/.

Está um bocado difícil de ler mas tenta perceber as diferenças.


here since 2009

Share this post


Link to post
Share on other sites
daj

Não utilizo muito C++ mas, com os streams da STL, deve ficar algo deste género:

int u, v, w;
ifstream rede("rede.txt");
if (!rede.is_open()) {
    cout << "Could not open file." << endl;
    return;
}

while (rede.good()) {
    bool valid = rede >> u >> v >> w;
    if (!valid) break;

    cout << "u = " << u << " v = " << v << " w = " << w << endl;
}

rede.close();

Os gurus de C++ que deixem mensagem a insultar-me se não estiver a fazer uma utilização correcta da biblioteca. :-)

Share this post


Link to post
Share on other sites
Miketo

Para o Localhost

A questão é que eu tenho de fazer a representação da rede com uma lista de adjacências, logo tenho de ter os ponteiros, não?

Eu considero que sei programar razoavelmente, o meu problema é não ter uma grande prática, logo há sempre funções que não conheço. Estou neste momento a estudar a STL (http://www.sgi.com/tech/stl/index.html) para ter uma noção das funções que há para me ajudar.

Pelo que percebi, o teu código está optimizado para o cálculo do caminho mais curto entre dois nós só, correcto?

Share this post


Link to post
Share on other sites
Localhost
A questão é que eu tenho de fazer a representação da rede com uma lista de adjacências, logo tenho de ter os ponteiros, não?

Não. Repara que no meu código eu não uso ponteiros e estou a trabalhar com o grafo como uma lista de adjacência. A diferença é que eu tenho uma queue por cada vértice do grafo que me vai representar todos os seus vértices adjacentes. Para além de ser mais fácil de implementar, é mais rápido.

Também podias ter um vector dentro da estrutura que representaria os vértices adjacentes. O problema é que ias desperdiçar espaço e podias ainda ter problemas de overflow. Com o vector a definição da minha estrutura seria:

const int MAX = 1000; // Pode ser qualquer valor 

typedef struct
{
    int dist;
    bool used;
    Edges edges[MAX]; // Vector com vértices adjacentes
} Vertex;

Pelo que percebi, o teu código está optimizado para o cálculo do caminho mais curto entre dois nós só, correcto?

Não. O Algoritmo de Dijkstra dá-te sempre o caminho mais curto entre um vértice e todos os outros do grafo. A variável que contém essa distância é a dist. Experimenta imprimir o valor dessa variável em todos os vértices e vais ver que contém realmente o valor do caminho mais curto.


here since 2009

Share this post


Link to post
Share on other sites
Miketo

Localhost:

Ok. Vou tentar perceber linha a linha o teu código para saber o que faz. Se é mais rápido e simples, melhor. Brigado pela dica. Desconhecia esta forma por completo  :(

daj

Brigado pela dica. Podes não ser guru do C++, mas resolveste o meu problema  :D Brigado.

Share this post


Link to post
Share on other sites
Miketo

Localhost

Estive a ver a tua solução e realmente é muito melhor. :) Consegui adaptar a tua solução ao que eu queria e já tenho isto fixolas. Brigado pela dica. :)

Share this post


Link to post
Share on other sites
Localhost

Deixa aí o código. Pode alguém precisar e ainda podes receber algumas dicas adicionais para o melhorares.


here since 2009

Share this post


Link to post
Share on other sites
Miketo

A rede tem de estar representada num ficheiro. A primeira linha tem o número de nós e arcos da rede (Apesar de ainda não ser usado esse valor). As restantes tem os extremos dos arcos e o seu custo. Começam por uma char 'a' que significa que é um arco, porque a ideia é poder colocar comentários (também ainda não está feito). Fica algo deste género:

3 3

a 1 2 5

a 1 3 2

a 2 3 2

O código é o seguinte:

#include <iostream>
#include <fstream>
#include <queue>	
#include <limits.h>	// inclui valor de infinito

using namespace std;

#define INF INT_MAX		//!< define INF como o maior numero inteiro possivel
#define pii pair< int, int >	//!< par arco - custo
#define piq pair <int, queue<Arcos> >	//!< par nó - fila de arcos

class Grafo{

private:

	int n;	//!< Número de nos da rede = sizeof excepto quando estico a rede

	//! Estrutura dos arcos
	typedef struct {
		int custo; 		//!< Custo do arco
		int destino;	//!< Destino - cabeça do arco
	} Arcos;

	//! Estrutura para Algoritmo de Dijkstra
	typedef struct {
		int nome;				//!< Nome do nó
		int distancia;			//!< Distancia - algoritmo dijkstra
		bool etiquetado;		//!< Nó está etiquetado, ou não? - algoritmo dijkstra
		int pred;				//!< Nó preecessor do no corrente - algoritmo dijkstra
	} Nodj;

	vector<piq> Rede;	//!< vector que representa a Rede

	//! Faz comparação
	struct comp {
		bool operator() (const pii &a, const pii &b) {
			return a.second > b.second;
		}
	};

	//! Fila que vai armazenar pares arco-custo por ordem crescente de custo
	priority_queue< pii, vector< pii >, comp > Q;

public:
	int Cria_Rede(char *ficheiro);	//!< Método que cria a Rede
	void MostraNosAdjacentes();		//!< Método que mostra a lista de nós adjacentes da rede
	int Pergunta();					//!< Método que pergunta nó origem de Dijkstra
	void Dijkstra(int from);		//!< Método que calcula o caminho mais curto de um nó à escolha para todos os outro

};

int Grafo :: Cria_Rede(char *ficheiro) {

int u, v, w, u2, v2, w2;	//!< Variáveis que recebem parametros dos arcos
int sz, i, j;	bool a;		//!< Variáveis auxiliares
int n, m;					//!< Número de nós e arcos da rede (do ficheiro)
char controlo;
Arcos ArcoNovo;	
vector<piq> temp;
queue<Arcos> arcos;

FILE *fich;

fich = fopen(ficheiro,"r");
fscanf(fich, "%d %d", &n, &m);	//!< Número de nós e arcos

while(!feof(fich)){
	fscanf(fich, "%c %d %d %d", &controlo, &u, &v, &w);

	if(controlo=='a'){	//!< É um arco
		if(u!=u2 || v!=v2 || w!=w2){	//!< Impede repetição de arcos
			u2=u;	v2=v;	w2=w;
			cout << u << " - " << v << " - " << w << endl;

			/***********************************************************
			* Como os ramos são bidireccionais, vai criar dois ramos
			* unidireccionais com o mesmo custo entre os nós em questão
			***********************************************************/

			//! Insere nó u na rede e seus arcos adjacentes
			ArcoNovo.destino = v;
			ArcoNovo.custo = w;

			sz = (int) temp.size();
			a=false;

			for (i=0; i<sz; i++){
				  if(temp.at(i).first==u){
					a=true;		//!< Se nó já existe no vector de nós
					j=i;
				}
			}

			if(!a){
				temp.push_back(piq(u, arcos));		//!< Introduz novo nó na Rede
				temp.back().second.push(ArcoNovo);	//!< Introduz arco adjacente ao novo nó				
			}
			else{
				temp.at(j).second.push(ArcoNovo);	//!< Introduz arco adjacente ao nó já existente
			}

			//! Insere nó v na rede e seus arcos adjacentes
			ArcoNovo.destino = u;
			ArcoNovo.custo = w;

			sz = (int) temp.size();
			a=false;

			for (i=0; i<sz; i++){
				if(temp.at(i).first==v){
					a=true;		//!< se nó já existe no vector de nós
					j=i;
				}
			}

			if(!a){
				temp.push_back(piq(v, arcos));		//!< Introduz novo nó na Rede
				temp.back().second.push(ArcoNovo);	//!< Introduz arco adjacente ao novo nó
			}
			else{
				temp.at(j).second.push(ArcoNovo);	//!< Introduz arco adjacente ao nó já existente
			}
		}		
	}
}
fclose (fich);	// fecha ficheiro

//! Ordenar nós	
sz = (int) temp.size();
for (i=0; i<sz; i++){
	for (j=0; j<sz; j++){
		if(temp.at(j).first==i+1){
			Rede.push_back(temp.at(j));
		}
	}
}

return sz;	//!< devolve numero de nós
}

void Grafo :: MostraNosAdjacentes(){

int sz, sz2, i, j;
Arcos head;

cout << endl;
sz = (int) Rede.size();	//!< Número de nós da rede
for (i=0; i<sz; i++){	//!< Vai percorrer a lista de cada um dos nós
	cout << i+1 << ": " << Rede.at(i).first << " --> ";
	sz2 = (int) Rede.at(i).second.size();	//!< Número de nós adjacentes
	for (j=0; j<sz2; j++){
		head = Rede.at(i).second.front ();
		cout << head.destino << "[" << head.custo << "] -> ";

		Rede.at(i).second.pop ();
		Rede.at(i).second.push(head);
	}
	cout << "NULL" << endl;	//!< Indica o fim da lista
}
}

int Grafo :: Pergunta(){

int no;

cout << endl << "Para sair introduza 0" << endl << "Qual o nó de origem:";
cin >> no;

return no;
}

void Grafo :: Dijkstra (int from){	//!< Recebe como parametro o nó de origem do cálculo

   int sznos = (int) Rede.size();	//!< Número de nós da rede
   vector<Nodj> Dijk;		//!< Vector para resolução do Algoritmo de Dijkstra
   Nodj Novo;

   int tamanho, total=0;	// Teste da Fila Q

   int sz, i, aux, u;

   Arcos v;

   //! Inicialização da struct com parâmetros do Algoritmo de Dijkstra
   for(i=0; i<sznos; i++){
	Dijk.push_back(Novo);	//!< Coloca novo nó no vector
	Dijk.at(i).nome = i+1;	//!< Nome do nó
	Dijk.back().distancia=INF;	//!< Distância inicial "infinita"
	Dijk.back().etiquetado = false;	//!< Não está etiquetado
	Dijk.back().pred = from;	//!< Inicialmente todos os nós tem como predecessor o nó origem
}

   Dijk.at(from-1).distancia = 0;	//!< Distância do nó origem a si próprio é nula
   Q.push(pii(from-1, 0)); 	//!< Coloca distância a si próprio na Fila Q
   tamanho = (int) Q.size();
   total=1;
   aux=sznos;

   // Algoritmo Dijkstra
   while(!Q.empty()) {
       u = Q.top().first;	//!< retira o nome do nó cabeça do arco adjacente com menor custo

       Q.pop();			//!< apaga par da fila Q

       if(Dijk.at(u).etiquetado)
		continue;	//!< Caso nó já esteja etiquetado passa para próxima iteração

       sz = (int) Rede.at(u).second.size();	//!< Número de nós adjacentes a u

       for(i=0; i<sz; i++) {

           v = Rede.at(u).second.front();	//!< Primeiro arco adjacente a u
           //! passa o arco para o fim da fila
           Rede.at(u).second.pop ();			
           Rede.at(u).second.push(v);

           if (Dijk.at(u).distancia + v.custo < Dijk.at((v.destino)-1).distancia){ 	
			//! caso a distancia do nó minPos + o custo do arco head seja menor que a dist do nó head
               Dijk.at((v.destino)-1).distancia = Dijk.at(u).distancia + v.custo;	//!< muda distancia
               Dijk.at((v.destino)-1).pred = Dijk.at(u).nome;	//!< muda o predecessor

               Q.push(pii(( v.destino)-1, Dijk.at((v.destino)-1).distancia));		//!< Coloca par na fila Q

               total++;

               if ( (int) Q.size() > tamanho )
				tamanho = (int) Q.size();
		}
       }
       Dijk.at(u).etiquetado = true;	//!< Nó u está etiquetado
   }
cout << "Total: " << total << " Tamanho max da Pilha Q: " << tamanho << endl << endl;

//! Escrita do caminho mais curto entre from e i+1
   for(i=0; i<sznos; i++){
	cout << " Distancia mínima de " << from << " a " << i+1 << ": " << Dijk.at(i).distancia << " - Caminho: ";
	cout << Rede.at(i).first;
	int p=i, temp;

	while (Dijk.at(p).pred!=from){
		cout << " <- " << Dijk.at(p).pred;
		temp = Dijk.at(p).pred;
		p = temp-1;
	}
	if( i+1 != from)
		cout << " <- " << from << endl;
	else
		cout << endl;
}
}

int main(){

int no, nodes;
Grafo a;	
char ficheiro[20];

cout << "Introduza o nome do ficheiro com a rede: ";
cin >> ficheiro;

nodes=a.Cria_Rede(ficheiro);

do{
	a.MostraNosAdjacentes();
	cout << endl;
	no=a.Pergunta();
	if(no>0 && no<=nodes)
		a.Dijkstra(no);
}while(no!=0);

return 0;
}

Share this post


Link to post
Share on other sites
Localhost

Excelente, utilizas uma Priority Queue, isso reduz-te o tempo de execução. Na minha implementação eu apenas utilizava uma queue e depois tinha de tirar o menor dela, o que resulta numa complexidade de: O(V²). A tua complexidade (não vi o código todo, mas considerando que não usas nada de especial para além da PQ) é de: O(E + V log(V)). Isto em worst-case, obviamente.


here since 2009

Share this post


Link to post
Share on other sites
Miketo

Sim. Eu comecei por implementar o teu código todo, mas depois ao analisar a coisa, vi que ele se calhar dava para optimizar. Como já tinha a priority queue feita, foi só substituir essa parte. Acho que tá fixe assim. Se entretanto melhorar alguma coisa que ache relevante vou colocando aqui. Pode sempre ajudar alguém.  :)

Share this post


Link to post
Share on other sites
Localhost

Agora que estive a ver mais um bocado do código, parece-me que estás a complicar um bocado.

A priority queue deve ser apenas constituída pelos nós do grafo, ou seja, ela vai conter as estruturas relativas aos nós do grafo. A partir daí deves retirar o mínimo dela (nó com menor distância até ao momento) e trabalhar a partir desse nó.

Parece-me que tens coisas desnecessárias como por exemplo, a variável etiquetado. Se tu retiras da priority queue os nós que já foram utilizados para quê que precisas de fazer aquela verificação?


here since 2009

Share this post


Link to post
Share on other sites
Miketo

Porque quando retiramos um nó da fila, vamos colocar os seus adjacentes nela, para serem analisados. Algum desses nós adjacentes pode já estar etiquetado, e assim não é necessário analisar mais esse. Assim faz o continue e passa para outro nó da fila.

Share this post


Link to post
Share on other sites
Localhost

O problema é que tu não estás a pensar correctamente na utilidade que a PQ vai ter.

A priority queue apenas vai conter (mal o programa inicia) todos os nós do grafo, ou seja, vai conter aquelas estruturas referentes ao grafo. Dentro dessas estruturas tens os nós adjacentes a esses mesmos nós. Quando analisas um nó (o com menor distância até ao momento) retiras esse nó da PQ e passas para outro.


here since 2009

Share this post


Link to post
Share on other sites
Miketo

Ou seja, pelo que dizes, deveria meter logo de início na priority queue todos os nós e a sua distância ao nó origem certo? Mas a questão, é que a PQ ordena os nós por custo, e inicialmente eles têm todos custo infinito, excepto o nó origem. Logo não ganho em colocar logo todos os nós na pilha. Certo?

O que eu faço é inicialmente meto o nó origem. Retiro, e desse nó, sei quais os nós adjacentes e esses são colocados na pilha ordenados pelo custo. E assim sucessivamente.

Confesso que não tou a ver como tás dizer  :)

Share this post


Link to post
Share on other sites
Localhost

Vou tentar fazer um post mais ou menos completo.

Vamos considerar este grafo para os efeitos: http://www.xatlantis.ch/examples/graphics/graph1_example.png e vamos imaginar que queremos determinar o caminho mais curto (em que a soma dos pesos das edges que utilizámos para chegar a um determinado nó seja a mínima) entre um dado nó (para o caso vamos considerar que queremos o primeiro nó (1)) e todos os outros nós do grafo. Imediatamente pensámos em resolver o problema com o Algoritmo de Dijkstra.

Temos então uma priority queue que inicialmente contem todos os vértices ou nós do grafo. Então pq = {1, 2, 3, 4, 5, 6}.

No primeiro passo (começámos no primeiro nó) vamos visitar todos os nós adjacentes a esse (2, 3 e 4). Como os valores desses nós são sempre INT_MAX então qualquer valor vai ser menor que esse e então actualizámos o valor de todos os nós adjacentes. Após visitarmos retirámos da PQ o primeiro nó. Então pq = {2, 3, 4, 5, 6}.

Agora vamos retirar o nó que contem a distância menor até ao momento (neste caso vai ser o 3º nó).

Repetimos o processo anterior até a PQ ficar vazia (pq = {}).

No final visitamos todos os nós e imprimimos o valor da distância contida neles.

Nota: Quando falo em retirar da PQ podemos atribuir ao valor da distância contida nele o valor de INT_MAX.


here since 2009

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.