Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  asdfasdf
Language: C/C++
Code:
// Programa en C para encontrar el camino de menor peso
// empleando el algoritmo de Dijkstra. La matriz mapa es una representación
// del grafo de ciudades conexas.
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
 
 
#define V 4 // Número de vertices en la ciudad.
#define SC 999999 // Cuando una ciudad no tiene conexión directa empleamos SC (Sin conexión)
 
// Impresión de resultados ----------------------
// Función para representar las ciudades empleando la matriz auxiliar auxCamino

 
// Función para mostrar el camino más corto 
void imprimirSolucion(int mSolucion[], int n, int auxCamino[], int dest)
{
    int i;
    printf("Viaje\t         Distancia\t");
 
    for (i = 1; i < V; i++)
    {
        if(i==dest){
        int x = i + 1;    
        printf("\nOrigen -> %d \t\t %d\t\t ", x, mSolucion[i] );
        }
    }
}
 
 
 
// Utilidad para encontrar el vertice con menor peso de un set de vertices que no han sido incluidos
// todavía en el árbol de caminos mínimos
int distanciaMinima(int mSolucion[], bool vertVisitado[])
{
    // Inicializamos valor min al máximo
    int min = INT_MAX, minimo;
    int v;
    for (v = 0; v < V; v++)
        if (vertVisitado[v] == false && mSolucion[v] <= min)
            min = mSolucion[v], minimo = v;
 
    return minimo;
}
 
 // Función que implementa el algoritmo de Dijkstra de camino más corto
 // para un mapa representado con una matriz de adyacencias.
 
void dijkstra(int mapa[V][V], int src, int dest)
{
    int mSolucion[V];  // La matriz de salida. mSolucion[i] guardara  
                       // los valores de menor distancia desde src hasta i
 
    // vertVisitado[i] será TRUE si el vértice i está incluido / es el más pequeño
    //  camino o el camino más corto en mSolucion desde src hasta i ha finalizado
    bool vertVisitado[V];
 
    // Matriz auxiliar para guardar el árbol con el camino más corto
    int auxCamino[V];
 
     // Inicializamos mSolucion como valores infinitos y vertVisitado como falso
    int i;
    for (i = 0; i < V; i++)
    {
        auxCamino[0] = -1; // Marcamos el origen 
        mSolucion[i] = INT_MAX;
        vertVisitado[i] = false;
    }
 
    // Distancia desde el vértice de inicio a sí mismo es siempre 0
    mSolucion[src] = 0;
 
    // Encuentra el camino más corto para todos los vértices
    int contador;
    for (contador = 0; contador < V-1; contador++)
    {
        // Escoge el vértice mSolucion mínimo de el conjunto de vértices sin procesar
        // u es siempre igual a src en la primera itineración
 
        int u = distanciaMinima(mSolucion, vertVisitado);
 
        // Marca el vértice escogido como visitado
        vertVisitado[u] = true;
 
        // Actualiza el valor de mSolucion de los vertices adyacentes del vértice escogido
 
        int v;
        for (v = 0; v < V; v++)
 
            // Actualiza mSolucion[v] solo si no está en vertVisitado,
            // hay un único arco de u a v y el peso total del camino
            // desde src a v es menor que el valor actual de mSolucion[v]
 
            if (!vertVisitado[v] && mapa[u][v] &&
                mSolucion[u] + mapa[u][v] < mSolucion[v])
            {
                auxCamino[v] = u;
                mSolucion[v] = mSolucion[u] + mapa[u][v];
            } 
    }
 
    // Imprime la matriz final construida.
    imprimirSolucion(mSolucion, V, auxCamino, dest);
}
 
 
int main()
{
 
    int mapa[V][V] = {{0,10,18,SC},{10,0,7,SC},{18,7,0,9},{SC,SC,9,0}};
    int dest, origen; // El destino es el número de la ciudad - 1.
    printf("¿Cual es la ciudad origen?: \n"); scanf("%d", &origen); origen--;
    printf("¿Cual es la ciudad destino?: \n"); scanf("%d", &dest); dest--;
    dijkstra(mapa, origen, dest);
 
    return 0;
}
          
          
Comments: