Grafos: camino mas corto entre dos nodos[c++]

[KINGARZA]

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 (cpp) [Seleccionar] Expandir


#include<bits/stdc++.h>
#define MAX 1000002
using namespace std;

vector<int>ady[MAX];
bool visitado[MAX];
int path[MAX];
int N;

//recorrido con recursion
void DFS(int u, int fin){
   path[N++] = u;
   visitado[u] = true;
   for(int v = 0; v < ady[u].size(); ++v)
       if(ady[u][v] == fin){
           path[N++] = fin;
           for(int i = 0; i < N; i++)
               cout<<path[i]<<" ";
           exit(0);
       }
       else if(!visitado[ady[u][v]])
           DFS(ady[u][v], fin);
}

//recorrido con cola
void DFS_cola(int u, int fin){
   queue<int>cola;
   cola.push(u);
   while(!cola.empty()){
       int tope = cola.front();
       visitado[tope] = true;
       path[N++] = tope;
       cola.pop();
       for(int v = 0; v < ady[tope].size(); ++v)
           if(ady[tope][v] == fin){
               path[N++] = fin;
               for(int i = 0; i < N; i++)
                   cout<<path[i]<<" ";
               exit(0);
           }
           else if(!visitado[ady[tope][v]])
               cola.push(ady[tope][v]);
   }

}

int main(){

   int n, a, b, m(0);
   cout<<"Dame numero de enlaces: ";
   cin>>n;

   for(int i = 0; i < n; i++){
       cin>>a>>b;
       ady[a].push_back(b);
       ady[b].push_back(a);
   }
   int inicial, fin;
   cout<<"Dame nodo raiz: ";
   cin>>inicial;
   cout<<"Dame nodo fin: ";
   cin>>fin;
   //DFS(inicial, fin);
   DFS_cola(inicial, fin);
   return 0;
}

[MAFUS]

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

[KINGARZA]

Gracias por contestar, ya intente eso que me comentas y aun asi me da el mismo resultado
.