elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Grafos: camino mas corto entre dos nodos[c++]
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Grafos: camino mas corto entre dos nodos[c++]  (Leído 3,819 veces)
KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Grafos: camino mas corto entre dos nodos[c++]
« en: 8 Noviembre 2016, 03:27 am »

Dados dos nodos A y V de un grafo, quiero encontrar el camino  (el mas corto) que empiece en A y culmine en V

POR EJEMPLO :



queremos iniciar en el nodo 1 y finalizar en el nodo 3

Entrada:
Dame numero de enlaces: 6
6 4
4 3
4 5
5 1
3 2
2 5
Dame nodo raiz: 1
Dame nodo fin: 3

Salida: 1 5 4 3

Error, lo optimo es: 1, 2, 3

Lo que intente primero fue recorrer a profundidad con recursion, luego con la cola (como el recorrido es por niveles crei que el recorrido seria optimo, pero no)pero ninguno me funciona, me han comentado que puedo hacerlo con backtracking, pero aun no entiendo muy bien esa tecnica y pues si pueden ayudarme, adelante.

Mi codigo
Código
  1. #include<bits/stdc++.h>
  2. #define MAX 1000002
  3. using namespace std;
  4.  
  5. vector<int>ady[MAX];
  6. bool visitado[MAX];
  7. int path[MAX];
  8. int N;
  9.  
  10. //recorrido con recursion
  11. void DFS(int u, int fin){
  12.    path[N++] = u;
  13.    visitado[u] = true;
  14.    for(int v = 0; v < ady[u].size(); ++v)
  15.        if(ady[u][v] == fin){
  16.            path[N++] = fin;
  17.            for(int i = 0; i < N; i++)
  18.                cout<<path[i]<<" ";
  19.            exit(0);
  20.        }
  21.        else if(!visitado[ady[u][v]])
  22.            DFS(ady[u][v], fin);
  23. }
  24.  
  25. //recorrido con cola
  26. void DFS_cola(int u, int fin){
  27.    queue<int>cola;
  28.    cola.push(u);
  29.    while(!cola.empty()){
  30.        int tope = cola.front();
  31.        visitado[tope] = true;
  32.        path[N++] = tope;
  33.        cola.pop();
  34.        for(int v = 0; v < ady[tope].size(); ++v)
  35.            if(ady[tope][v] == fin){
  36.                path[N++] = fin;
  37.                for(int i = 0; i < N; i++)
  38.                    cout<<path[i]<<" ";
  39.                exit(0);
  40.            }
  41.            else if(!visitado[ady[tope][v]])
  42.                cola.push(ady[tope][v]);
  43.    }
  44.  
  45. }
  46.  
  47. int main(){
  48.  
  49.    int n, a, b, m(0);
  50.    cout<<"Dame numero de enlaces: ";
  51.    cin>>n;
  52.  
  53.    for(int i = 0; i < n; i++){
  54.        cin>>a>>b;
  55.        ady[a].push_back(b);
  56.        ady[b].push_back(a);
  57.    }
  58.    int inicial, fin;
  59.    cout<<"Dame nodo raiz: ";
  60.    cin>>inicial;
  61.    cout<<"Dame nodo fin: ";
  62.    cin>>fin;
  63.    //DFS(inicial, fin);
  64.    DFS_cola(inicial, fin);
  65.    return 0;
  66. }


« Última modificación: 8 Noviembre 2016, 03:34 am por KINGARZA » En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Grafos: camino mas corto entre dos nodos[c++]
« Respuesta #1 en: 8 Noviembre 2016, 09:22 am »

En tu ejemplo te faltó el camino 1 - 2 por definir, por eso programa no podía verlo y te dio 1 - 5 - 4 - 3


En línea

KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Re: Grafos: camino mas corto entre dos nodos[c++]
« Respuesta #2 en: 9 Noviembre 2016, 20:38 pm »

Gracias por contestar, ya intente eso que me comentas y aun asi me da el mismo resultado
 :-[.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Diferentes caminos entre dos nodos en un grafo
Programación General
dark_headhunter 2 10,023 Último mensaje 14 Julio 2011, 05:01 am
por pucheto
Medir el ancho de banda entre dos nodos en una LAN
Redes
madpitbull_99 2 13,754 Último mensaje 3 Agosto 2011, 01:50 am
por Kasswed
Implementación del camino más corto de la matriz Laberinto de tamaño NxN
Java
charry2012 0 3,547 Último mensaje 13 Septiembre 2012, 06:51 am
por charry2012
Ubuntu sigue su camino hacia la convergencia entre móvil y PC: así están hoy ...
Noticias
wolfbcn 0 1,353 Último mensaje 8 Septiembre 2015, 14:52 pm
por wolfbcn
Ayuda, Camino mas corto
Programación C/C++
RRjavier21 1 1,685 Último mensaje 22 Diciembre 2018, 12:09 pm
por CalgaryCorpus
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines