dantzig - shortest path algorithm python

¿Encontrar los caminos kth-shortest?

Question

Encontrar el camino más corto entre dos puntos en un gráfico es una pregunta de algoritmos clásicos con muchas buenas respuestas ( algoritmo de Dijkstra , Bellman-Ford , etc.) Mi pregunta es si hay un algoritmo eficiente que, dado un gráfico dirigido, ponderado, un par de los nodos s y t, y un valor k, encuentra la ruta k-shortest entre s y t. En el caso de que haya varias rutas de la misma longitud que todas las vinculadas para la k-más corta, está bien que el algoritmo devuelva cualquiera de ellas.

Sospecho que este algoritmo probablemente se pueda hacer en tiempo polinomial, aunque soy consciente de que podría haber una reducción del problema de la ruta más larga que lo haría NP-difícil.

¿Alguien sabe de tal algoritmo, o de una reducción que muestre que es NP-hard?

Answer 1

Aunque la pregunta tiene una respuesta válida aceptada, esta respuesta aborda el problema de la implementación al proporcionar un código de trabajo de muestra. Encuentre el código válido para la ruta más corta kth aquí:

// Complejidad del tiempo: O (V k (V * logV + E))

using namespace std;

typedef long long int ll;
typedef short int i16;
typedef unsigned long long int u64;
typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

const int N = 128;

struct edge
{
    int to,w;
    edge(){}
    edge(int a, int b)
    {
        to=a;
        w=b;
    }
};

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

priority_queue <el> pq;

vector <edge> v[N];

vector <int> dist[N];

int n,m,q;

void input()
{
    int i,a,b,c;
    for(i=0;i<N;i++)
        v[i].clear();
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a++;
        b++;
        v[a].push_back(edge(b,c));
        v[b].push_back(edge(a,c));
    }
}

void Dijkstra(int starting_node, int ending_node)
{
    int i,current_distance;
    el curr;
    for(i=0;i<N;i++)
        dist[i].clear();
    while(!pq.empty())
        pq.pop();
    pq.push(el(starting_node,0));
    while(!pq.empty())
    {
        curr=pq.top();
        pq.pop();
        if(dist[curr.vertex].size()==0)
            dist[curr.vertex].push_back(curr.cost);
        else if(dist[curr.vertex].back()!=curr.cost)
            dist[curr.vertex].push_back(curr.cost);
        if(dist[curr.vertex].size()>2)
            continue;
        for(i=0;i<v[curr.vertex].size();i++)
        {
            if(dist[v[curr.vertex][i].to].size()==2)
                continue;
            current_distance=v[curr.vertex][i].w+curr.cost;
            pq.push(el(v[curr.vertex][i].to,current_distance));
        }
    }
    if(dist[ending_node].size()<2)
        printf("?/n");
    else
        printf("%d/n", dist[ending_node][1]);
}

void solve()
{
    int i,a,b;
    scanf("%d", &q);
    for(i=1;i<=q;i++)
    {
        scanf("%d %d", &a, &b);
        a++;
        b++;
        Dijkstra(a,b);
    }
}

int main()
{
    int i;
    for(i=1;scanf("%d %d", &n, &m)!=EOF;i++)
    {
        input();
        printf("Set #%d/n", i);
        solve();
    }
    return 0;
}

Answer 2

El mejor (y básicamente óptimo) algoritmo se debe a Eppstein .

Answer 3

Está buscando el algoritmo de Yen para encontrar K caminos más cortos. La k vía más corta será la última ruta en ese conjunto.

Aquí hay una implementation del algoritmo de Yen.

Y aquí está el documento original que lo describe.