(void *) blog

Posted on by fortytwo_de


Existen varios algoritmos para buscar la ruta óptima entre dos puntos de un grafo. El más común y fácil de implementar es el Algoritmo de Dijkstra. Es una forma sencilla de encontrar el camino óptimo a un nodo del grafo teniendo en cuenta los costes de pasar por un borde.

¿Qué es un grafo?

La definición formal de "grafo" es (c&p de Wikipedia)

Un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

En la imagen, los nodos son los cuadrados grises; los arcos son las flechas. En este post me voy a centrar en los digrafos (grafos dirigidos) ponderados, es decir, aquellos en los que el arco (u, v) no es igual al arco (v, u) y tienen pesos asociados a los arcos.

Una arista en un grafo dirigido se considera desde x hasta y, siendo y la cabeza y x la cola.

El algoritmo de Dijkstra

Simplificando el algoritmo, el algoritmo de Djikstra para buscar la ruta más corta entre dos puntos de un grafo es utilizar Breadth-First Search (algoritmo explicado en esta entrada) y rehacer el recorrido siguiendo las mínimas distancias.

El problema del algoritmo de Djikstra es que la propia demostración asume que las ponderaciones de los arcos son positivas:

Clearly, the claim is true for v1 = s, since d[s] = shortest_distance(s) = 0 and all edge weights are positive...

Bellman-Ford salva el día

El algoritmo de Bellman-Ford aparece porque, aunque los digrafos ponderados con pesos positivos son suficientes en la mayoría de ocasiones, hay casos en los que es necesario reducir el coste final de una ruta.

Es un caso un poco anti-intuitivo cuando se piensa en términos de distancias, porque una distancia negativa es físicamente imposible. No obtante, si la variable que interesa optimizar no es la distancia, entonces los pesos no-negativos son más razonables.

Harrichu y la competición ciclista

Se puede descargar el enunciado del problema aquí.

El problema es básicamente una implementación directa del algoritmo de Bellman-Ford, con un poco de interpretación de resultados al final. Los únicos puntos importantes son:

  • Se empieza en el nodo 0.
  • El objetivo es el nodo n-1.
  • Hay que detectar ciclos con pesos negativos.

Implementación

En C++. Se me ha pegado la manía.

Definciones globales:

#include <iostream>
#include <vector>
using namespace std;

#define INFINITY 100000000

bool negative_cycle = false;

Nota: es más correcto utilizar INT_MAX para definir INFINITY, pero el Juez de la Olimpiada dice que esa expresión no está definida (?)

El tipo para representar aristas:

struct edge_t {
    int source;
    int destination;
    int weight;

    edge_t(int source_n, int destination_n, int weight_n) : source(source_n), destination(destination_n), weight(weight_n) {}
};

La función para calcular la matriz Bellman-Ford de distancias devuelve el tipo vector<int>, siendo cada elemento la mínima distancia a un vértice dado.

vector<int> bellman_ford(vector<edge_t> graph, int nodes) {
    vector<int> fatigues(nodes, INFINITY);
    fatigues[0] = 0;

    for(size_t x = 0; x < nodes-1; x++) {
        for(size_t i = 0; i < graph.size(); i++) { // relax ALL the edges!
            if(fatigues[graph[i].source] + graph[i].weight < fatigues[graph[i].destination] && fatigues[graph[i].source] != INFINITY) {
                fatigues[graph[i].destination] = fatigues[graph[i].source] + graph[i].weight;
            }
        }
    }

    /* Relax all the edges one more time. If the fatigue changes,
       then the graph must contain at least one negative cycle. */

    for(size_t i = 0; i < graph.size(); i++) {
        if(fatigues[graph[i].source] + graph[i].weight < fatigues[graph[i].destination] && fatigues[graph[i].source] != INFINITY) {
            negative_cycle = true;
        }
    }

    return fatigues;
}

Y finalmente, main:

int main() {
    int nodes, x, y, c;
    cin >> nodes;
    vector<edge_t> graph;

    while(cin >> x >> y >> c && x != -1)
        graph.push_back(edge_t(x, y, c));

    vector<int> fatigues = bellman_ford(graph, nodes);
    if(fatigues[nodes-1] == INFINITY) {
        cout << "No hace falta que empieces" << endl;
    } else {
        if(negative_cycle == true) {
            cout << "Harrichu no se cansa" << endl;
        } else {
            cout << fatigues[nodes-1] << endl;
        }
    }

    return 0;
}

El código se puede ver completo en hastebin.

Posted on by fortytwo_de | Posted in Algoritmos, C, Matemáticas, Programación


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>