Dijkstra算法-无限循环

Question

作为作业作业，我将使用指向每个顶点的链接列表的一系列指针来实现一个邻接列表。每个链表都有一个元素<destination>，该元素表示邻接列表顶点的顶点邻居。

邻接列表是无向和无加权的，所以我把所有的权重都处理为1。

 /* Adjacency List Node data structure (edge)
 * Linked List data structure for storing linked vertices
 */
struct adjacencyListNode
{
    int destination;
    struct adjacencyListNode *next;
};

/* Adjacency List Vertex data structure (vertex)
 * <AdjacencyList> consists of pointers to <n> adjacencyListVertex
 */
struct adjacencyListVertex
{
    struct adjacencyListNode *head;
};

我试图在邻接列表上执行Dijkstra的算法，以找到从s到t的最小路径。

现在，我正在实现以下算法：

/* Prints the length and path taken of the shortest path in adjacency list between s and t.
 *  Uses Dijkstra’s algorithm to compute shortest path.
 *  S: source vertex
 *  V: destination vertex
 */
void shortestPath(int s, int t) {
    int known[size]; // shortest distance to vertex is know
    int cost[size]; // distance from source <s> to each vertex
    int path[size]; //path

    // Initialization: Set all distances to infinity (represented by -1), since arrays have not been visited and graph is positively weighted
    for (int index = 0; index<size; index++) {
        cost[index] = INFINITY;
        known[index] = 0;
    }

    // Set distance from source->source to 0
    cost[s-1] = 0;

    // Starting at s, traverse towards all reachable unvisited verticies, visit it and repeat
    while (isFinished(known, size) == false) {
        // Select a vertex from list of unvisited nodes which has the smallest cost
        int cheapestVertex, cheapestValue = INFINITY+1;
        for (int costCheck = 0; costCheck<size; costCheck++) {
            if ((known[costCheck] == 0) && (cost[costCheck] < cheapestValue)) {
                // We found a cheaper unvisited vertex
                //                  cout << "Cheapest vertex: " << costCheck << endl;
                cheapestVertex = costCheck;
                cheapestValue = cost[cheapestVertex];
            }
            //              cout << "found? " << cheapestVertex << " " << cheapestValue << endl;
        }


        //          cout << "Cheapest vertex: " << cheapestVertex << endl;
        // For each unvisited neighbor of our cheapest (unvisited) vertex
        adjacencyListNode* iterator = A[cheapestVertex].head; // iterator is our first neighbor
        while (iterator)
        {
            // Calculate the new cost from the current vertex <cheapestVertex>
            if (cost[cheapestVertex]+1 < cost[iterator->destination] && known[iterator->destination] == 0) {
                cost[iterator->destination] = cost[cheapestVertex]+1;
            }
            iterator = iterator->next; // move to next neighbor, repeat
        }

        //          cout << "Cheapest vertex: " << cheapestVertex  << " known." << endl;
        // Mark the current vertex <cheapestVertex> as visited
        known[cheapestVertex] = 1;

        // DEBUG: (REMOVE BEFORE SUBMISSION)
        for (int i = 0; i<size; i++) {
            cout << "Vertex " << i << " : known? " << known[i] << ", cost? " << cost[i] << endl;
        }
        cout << endl;

        if (cost[t-1] != INFINITY) break; // We already know shortest path, end.
    }

    // We know the shortest path cost to t
    cout << "Cost to t: " << cost[t] << endl;
}

bool isFinished(int array[], int arraySize) {
    bool finished = true;
    for (int iterator=0; iterator < arraySize; iterator++) {
        if (array[iterator] == 0) {
            // vertex not known, we're not done.
            finished = false;
        }
    }
    return finished;
}

我正在传递以下输入，它只是添加指定的相关顶点并调用我的最短路径算法。

0 1
1 2
1 3
2 4
3 5
5 38
6 7
6 10
8 9
11 12
12 13
12 15
12 21
13 14
14 15 
16 17
17 18
18 19
19 20
20 39
21 22
22 23
22 31
23 24
23 32
24 25
24 33
25 26
26 27
27 28
28 29
29 30
31 40
34 35
34 37
35 36
36 37
1
shortest-path

我的代码遍历0->1->2->3->4->5->38，然后无限重复38。

有人知道我的问题在哪里吗？

Answer 1

你有一些问题。因为这是家庭作业，我不会给你完整的答案。

问题1:如果存在无法从s访问的节点，会发生什么情况？这就是在你的例子中正在发生的事情。

提示:您需要确定何时停止循环(除了您已经拥有的循环)。看看你最便宜的选择--你怎么确定没有有效的？

提示2-如果所有剩余的顶点都有INFINITE的成本，当前循环将不会为INFINITE设置值，因此您将使用未初始化的值。也许在开始之前检查一下你找到的最便宜的费用是多少。

问题2：cost[iterator->destination] = cost[cheapestVertex]+1;

提示:你确定每次这样做都是正确的吗？如果节点已经有了更低的成本，或者已经被访问了呢？

问题3:一旦你知道了t，你就可以停止寻找。不需要检查整个图表。注意:这是一个您不一定需要的更改，因为没有它，您的代码就能工作。