Модифицировать алгоритм Дейкстры с некоторыми условиями - PullRequest
Новая
       39

Модифицировать алгоритм Дейкстры с некоторыми условиями

0 голосов
/ 04 мая 2019

Для неориентированного графа с затратами на ребрах найдите кратчайший путь от заданного узла A к B. Скажем так: кроме затрат и ребер, мы начинаем в момент времени t = 0, и для каждого узла вам даетсяперечислите с некоторыми временами, что вы не можете пройти через эти узлы в это время, и вы не можете ничего сделать за это время, вам нужно подождать, пока «это пройдет».Как говорится в заявлении, вы являетесь заключенным, и вы можете телепортироваться через камеры, а время телепортации требует затрат времени, когда вы не можете ничего сделать, когда стражник находится с вами в камере, и ониНаходитесь в клетке в каждой отметке времени, указанной в списке, найдите минимальное время, чтобы убежать из тюрьмы.

То, что я пытался:

Я пытался изменить это так: в обычном диджстре выпроверьте, является ли он опекуном в минимальное время, которое вы найдете для каждого узла, но он не сработал ... какие-либо другие идеи? 

int checkGuardian(int min, int ind, List *guardians)
{
    for (List iter = guardians[ind]; iter; iter = iter->next)
        if(min == iter->value.node)
            return min + iter->value.node;

    return 0;
}

void dijkstra(Graph G, int start, int end, List *guardians)
{
    Multiset H = initMultiset();

    int *parent = (int *)malloc(G->V * sizeof(int));

    for (int i = 0; i < G->V; ++i)
    {
        G->distance[i] = INF;
        parent[i] = -1;
    }

    G->distance[start] = 0;

    H = insert(H, make_pair(start, 0));

    while(!isEmptyMultiset(H))
    {
        Pair first = extractMin(H);

        for (List iter = G->adjList[first.node]; iter; iter = iter->next)
            if(G->distance[iter->value.node] > G->distance[first.node] + iter->value.cost 
                                                + checkGuardian(G->distance[first.node] + iter->value.cost, iter->value.node, guardians))
            {
                G->distance[iter->value.node] = G->distance[first.node] + iter->value.cost 
                                                + checkGuardian(G->distance[first.node] + iter->value.cost, iter->value.node, guardians);
                H = insert(H, make_pair(iter->value.node, G->distance[iter->value.node]));
                parent[iter->value.node] = first.node;
            }
    }

    printf("%d\n", G->distance[end]);
    printPath(parent, end);
    printf("%d\n", end);
}

с этими структурами: 

typedef struct graph
{
    int V;
    int *distance;
    List *adjList;
} *Graph;

typedef struct list
{
    int size;
    Pair value;
    struct list *tail;
    struct list *next;
    struct list *prev;
} *List;

typedef struct multiset
{
    Pair vector[MAX];
    int size;
    int capacity;
} *Multiset;

typedef struct pair
{
    int node, cost;
} Pair;

КакНа входе вам дается количество узлов, количество ребер и начальный узел.Для следующего числа линий ребер, которые вы читаете, и ребра между 2 узлами и стоимостью, связанной с этим ребром, затем для следующего числа линий ребер вы читаете символ «N», если вы не можете выйти из этой ячейки, и «Y "если вы можете сбежать из этой ячейки, тогда число хранителей временных меток будет в том числе временных отметок, временных отметок.Для этого ввода: 

6 7 1
1 2 5
1 4 3
2 4 1
2 3 8
2 6 4
3 6 2
1 5 10
N 0
N 4 2 3 4 7
Y 0
N 3 3 6 7
N 3 10 11 12
N 3 7 8 9

Я ожидал бы этот вывод: 

12
1 4 2 6 3

Но я получаю этот вывод: 

10
1 4 2 6 3
...