graph - 用一些条件修改dijkstra的算法

Question

给定一个边上有成本的无向图，找到从给定节点 A 到 B 的最短路径。让我们这样说：除了成本和边，我们从时间开始t = 0，对于每个节点，你都会得到一个列表，其中包含你那个时候不能通过那些节点，那个时候你什么也做不了，你必须等到“它通过”。正如声明所说，你是一名囚犯，你可以通过牢房传送，而传送时间需要边缘时间的成本，而那些你无能为力的时间是当一个监护人与你在牢房中时，他们列表中给出的每个时间戳都在牢房中，找到逃离监狱的最短时间。

我尝试了什么：

我试图这样修改它：在正常的dijkstra中，您在为每个节点找到的最短时间检查它是否是监护人，但它没有用..还有其他想法吗？

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

标签： graphdijkstraundirected-graph