Ayuda con mi proyecto de grafos

[Akai]

Sin ánimo de ofender, Maurice_Lupin:

Si no entiendes de grafos, no líes más la perdiz, en este caso los grafos abstraen todo el trabajo de las coordenadas en simples relaciones entre puntos. No intentemos reinventar la rueda, este caso no lo necesita.

[JorgeKun]

entiendo su punto pero vera en un proyecto para la facultad donde se nos pidio emplear grafos para dicho proposito y si he estado tratando con una rchivo pero me da problemas , sigo revisando el codigo.
Creo que optare por hacer la matriz de adyacencia de 45x45, aunque espero terminar...es para mañana 
Gracias por su tiempo 

[Maurice_Lupin]

Pues si me ofendiste y no creo haber reinventado nada.

[JorgeKun]

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <conio.h>

#define MaxNodos 10

typedef struct nodo_ {
    int etiqueta;
    float peso;
    struct nodo_ *sig;
}Tnodo;

/** variables globales */
Tnodo *Lista[MaxNodos]; //lista de adyacencia
int marca[MaxNodos]; //visitados
int predecesores[MaxNodos]; //ruta
float d[MaxNodos]; // distancia - peso
int Num_Vertices; //numero de vertices
int tipo; //1 no dirigido, 0 dirigido
/** ------------------ */

/* Inicializa la lista de adyacencia a NULL */
void init() {
    int i;
    for (i = 0; i < MaxNodos; i++)
        Lista[i] = NULL;     
}

/* Muestra la lista de adyacencia (un simple debug) */
void mostrar_lista_adyacencia () {
   Tnodo *q;
   int i;
   
   for (i = 0; i < Num_Vertices; i++) {
      if (Lista[i] != NULL) {
         q = Lista[i];
         printf ("vertice %d: ", i);
         while (q) {
            printf ("%d ", q->etiqueta);
            q = q->sig;
         }
         printf("\n");
      }
   }
}

/* Inserta los vertices en la lista de adyacencia */
void inserta (int Vorigen, int Vfinal, float peso) {
    Tnodo *q;
    q = (Tnodo*) malloc (sizeof(Tnodo) * 1);
    if (!q) return; //hubo un error
    q->etiqueta = Vfinal-1;
    q->peso     = peso;
    q->sig      = NULL;
    if (Lista[Vorigen-1] != NULL)
       q->sig = Lista[Vorigen-1];
    Lista[Vorigen-1] = q;
}

/* Libera la lista de adyacencia */
void liberar_lista (void) {
   Tnodo *q;
   int i;
   for (i = 0; i <  Num_Vertices; i++) {
      if (Lista[i] != NULL) {
         while (Lista[i] != NULL) {
            q = Lista[i];
            Lista[i] = Lista[i]->sig;
            free(q);
         }
      } //--fin si (no necesarias las llaves)
   } //--fin for (no necesaria las llaves)
}

/* Carga el grafo desde un fichero */
void cargar_grafo (char *fn) {
  FILE *fp;
  int v_in, v_fn; //vertice inicial y final
  float peso;
  if ((fp = fopen (fn, "r")) == NULL) {
       printf ("El archivo %s no existe o no se puede abrir\n", fn);
       getche();
       exit(0);
   }
   fscanf (fp, "%d\n", &tipo); //tipo es una vble global
   fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global
   while (!feof(fp)){
         fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
         inserta(v_in, v_fn, peso);
         inserta (v_fn, v_in, peso);
   }
   fclose (fp);
} // fin cargar_grafo

/* Retorna el peso de la arista que une dos nodos */
float return_peso (int origen, int destino) {
   Tnodo *p;
   int encontrado;
   
   encontrado = 0;
   p = Lista[origen];
   while (p != NULL && !encontrado) {
      if (p->etiqueta == destino)
        encontrado = 1;
      else
        p = p->sig;
   }
   return p->peso;
}


int menor_valor() {
   int i, verticeMenor;
   float menor;
   menor = INT_MAX;
   for (i = 0; i < Num_Vertices; i++) {
      if (marca[i] == 0 )
         if (menor > d[i]) {
            menor = d[i];
            verticeMenor = i;
         }
   } // fin for
   return verticeMenor;
}

/* Dijkstra */
void dijkstra (int origen, int destino)
{
   int i, last, x;
   Tnodo *p;
   // inicializacion
   for (i = 0; i < MaxNodos; i++) {
      d[i] = INT_MAX; //"infinito"
      marca[i] = 0;
      predecesores[i] = -1;
   }
   // --
   d[origen] = 0;
   marca[origen] = 1;
   last = origen;
   while (marca[destino] == 0) { //hasta que no lleguemos al destino
      p = Lista[last];
      while (p != NULL){   //para todos los nodos adyacendes
          if (marca[p->etiqueta] == 0) //si no ha sido visitado
          if (d[p->etiqueta] > d[last] + return_peso(last, p->etiqueta))
              {
              d[p->etiqueta] = d[last] + return_peso(last, p->etiqueta);
              predecesores[p->etiqueta] = last;
          } // fin si
           p = p->sig;
      } // fin mientras
      x = menor_valor();   
      marca[x] = 1;
      last = x;
   } // fin mientras
}

/* Imprime la ruta por pantalla */
void ImprimirCamino(int v) {
   if (v != -1)
      ImprimirCamino(predecesores[v]);
   if (v != -1) //evitamos que se imprima el -1
      printf("%d ",v+1);
}

/* Menu de opciones */
int menu() {
    int opcion;
    do {
        printf ("\n[0] Salir\n");
        printf ("[1] Calcular ruta\n");   
        printf ("Opcion: ");
        scanf("%d", &opcion);
    }while (opcion < 0 || opcion > 1);
    return opcion;
}

/* Funcion principal */
int main () {
    char file[25];
    int origen, destino;
    int salir = 0;
    printf ("Cargar fichero?: ");
    scanf("%s", file);
    init();
    cargar_grafo(file);
    mostrar_lista_adyacencia(); //debug
    do {
        switch(menu()) {
            case 0:
                 salir = 1;
                 break;
            case 1:
                  do {
                      printf ("Vertice origen: "); scanf("%d", &origen);
                      printf ("Vertice destino: "); scanf("%d", &destino);
                      if (origen < 1 || origen > MaxNodos || destino < 1 || destino > MaxNodos)
                           printf ("Error: El rango tiene que estar comprendido entre 1 y %d\n", Num_Vertices);
                  }while (origen < 1 || origen > Num_Vertices || destino < 1 || destino > Num_Vertices);   
                  dijkstra(origen-1, destino-1);
                  ImprimirCamino(destino-1);
                  break;         
        }; //final switch
    }while(!salir);   
    liberar_lista();
}

Este codigo lo encontre navegando por ahiy empeze a basarme en el, veran funciona bien el problema es que no entiendo la manera en que me carga el archivo.
He estado experimentando un poco y al poner en el .txt "1 2 3" entiendo que lo toma como ,nodoOrigen,Costo,nodoDestino, pero aun asi me pierdo durante la ejecucion del codigo y no me entrega las distancias :/, espero me puedan ayudar a entender como abre el archivo porfavor y como lo trabaja, ya que ese es mi problema, gracias de antemano 

[Akai]

El archivo debería ser algo así por la forma en la cual lo estás leyendo:

Código [Seleccionar] Expandir


1
5
0 1 15
3 4 20
2 0 4
4 2 7


siguiendo el patrón:
tipo
numero de vertices
arista
arista
arista
...


no estoy demasiado seguro que estuvieses siguiendo ese patrón.

[JorgeKun]

Tienes razon yo seguia un patron Origen---Costo de arista----Destino,
pero solo una duda, disculpa si sueno muy noob, pero al llegar a las aristas en tu ejemplo como esta declarado, ejemplo:
0    1    15
el primero y ultimo son los nodos y el de enmedio es el costo? o estoy entendiendo mal? 

[Akai]

Eso está en tu propio código. Yo únicamente me he dedicado a crear un ejemplo siguiendo el patron de lectura:

Código (c) [Seleccionar] Expandir

void cargar_grafo (char *fn) {
   fscanf (fp, "%d\n", &tipo); //tipo es una vble global
   fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global
   while (!feof(fp)){
         fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
         inserta(v_in, v_fn, peso);
         inserta (v_fn, v_in, peso);
   }
} // fin cargar_grafo

[JorgeKun]

Primero que nada muchas gracias ya entendi perfectamente mi error, y tambien que el proyecto es poco eficiente pero en fin es tarea xD.
Segundo esa parte del archivo no es codigo mio por eso no entendia que hacer pero gracias a su ayuda ya lo entendi!!!
Muchas gracias!!, espero serle util a alguien tambien algun dia 
Mas tarde posetare el resultado final y ya mañana les dire que tal me fue presentadolo ante mi clase

[JorgeKun]

Bueno el proyecto funciono muy bien , sin embargo me fue muy mal y tendre que presentarlo de nuevo todo debido a que no imprimi el grafo en manera de grafica, yo lo imprimi en un simple listado