最短路径问题（有负边值）

发表于 更新于 分类于

上一篇我们使用了Dijkstra算法来解决最短路径问题，但这个算法有一个局限性，图不能存在负值边，因为Dijkstra算法的策略是贪心算法。

使用Dijkstra算法得到错误的解

贪心算法对于问题只需考虑当前局部信息，然后就要做出决策，也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。因此该算法具有局限性, 若应用不当, 不能保证求得问题的最佳解（正确解）。例如，下面的图存在负边，那么贪心算法将可能得不到正确的解。

我们用Dijkstra算法的流程走一遍。我们将a作为起点，首先将a的known置为1，然后更新其邻接的边，a->c 为4 ，a->b 为6 ，此阶段结束。然后我们寻找最小的未知的节点，也就是c，c没有邻接的节点，此阶段结束。最后我们选择b，由于b唯一邻接的c点的known为1，是已知的，所以此阶段也结束。最后我们使用Dijkstra算法得到的结果是a->c 长度为4，a->b 长度为6。但这是错误答案，a->c 最短的路径为3，不是4，最短路径为 a->b->c 。

从上面的分析可以看出，具有负边的图，局部最优策略不能产生全局最优解，两者没有任何关系，所以不能使用贪心策略，不能使用Dijkstra算法。

正确的计算方式

那么该如何处理具有负边值的图呢？

一个诱人的方案是将每条边都加上一个常数，如此消去图中所有的负值边，计算出新的最短路径，然后将结果用在原来的图上。我们拿上面的图来举例子。
要消去负值边，那么每条边都要加上3，如下图。

img

新计算的最短路径为 a->c ，但实际上的最短路径为 a->b->c， 出现了错误，因为有许多条边的路径比有较少条边的路径权值更重了，每多一条边，就多一份增加的权值。此种方法不能使用。

将赋权的无权的算法相结合可以解决这个问题，但要付出运行时间激烈增长的代价。
我们需要舍弃已知顶点的概念，因为这个算法需要能够改变它的意向。

大致过程如下：

  1. 将顶点s放入队列中。
  2. 让一个顶点v出列，找出所有与v相邻接的顶点w。
  3. 如果 dw > dv + C(v,m)，就更新dw和pw，而且若w此时不在队列中，需要将其入列。注：C(v,m)是从v点到w的距离
  4. 重复2、3过程直至队列为空。

我们以1-1中的图为示例，顶点a作为起点，这个图的邻接表为图1-2，和之前略微不一样的是value中的链表头是一个false、true，这个字段的意思就是表明此顶点是否在队列中。


放大一下看图2-1吧，一切尽在不言中…（敷衍，哼）

img

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
邻接表节点
*/
typedef string vertex;
struct Node
{
    vertex data;
    int weight = 0;
    Node *next = NULL;

    Node(vertex data,int weight, Node *next = NULL)
    {
        this->data = data;
        this->weight = weight;
        this->next = next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
/*头，用于存放此节点是否在队列中的信息*/
struct Header
{
    bool isInQueue = false;//是否在队列中
    Node *next = NULL;

    Header(Node* n)
    {
        next = n;
    }
};
1
2
3
4
5
6
7
8
9
/*
表  考虑负边
*/
const int INFINITE = 9999999;  //距离 定义无限大
struct Box
{
    int dv = INFINITE;
    vertex path;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//计算最短路径
map<vertex, Box*> ShortestPath(vertex s, map<vertex, Header*> graph)
{
    //初始化盒子
    map<vertex, Box*> boxs = initBox(s, graph);
    queue<vertex> queue;
    queue.push(s);

    //如果队列不为空
    while (!queue.empty())
    {
        vertex v = queue.front();
        queue.pop();
        graph[v]->isInQueue = false;

        Node *n = graph[v]->next;
        //依次查询队头的邻接顶点
        while (n != NULL)
        {
            if (boxs[v]->dv + n->weight < boxs[n->data]->dv)
            {
                //更新dv
                boxs[n->data]->dv = boxs[v]->dv + n->weight;
                //更新pv
                boxs[n->data]->path = v;
                //如果队列中不存在，入队
                if (graph[n->data]->isInQueue == false)
                {
                    queue.push(n->data);
                    graph[n->data]->isInQueue = true;
                }
            }
            n = n->next;
        }
    }
    return boxs;
}

代码执行结果及完整代码
img