跳转至

求有负值边的图的最短路

若图中有负权环路，则会产生无穷循环，最短路不存在

C
 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
38
39
40
41
42
43
44
45
46
void bellmanFord(struct Graph* graph, int src) {
    int V = graph->V;
    int E = graph->E;
    int* dist = (int*)malloc(V * sizeof(int));

    // 初始化距离数组
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;

    // 松弛操作
    for (int i = 1; i <= V - 1; i++) {
        //V-1轮对于遍历每条边更新是肯定够的，就算是考虑退化为一条单链表，也只需要V-1次
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 检测负权环
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            //判断有负权环的条件是，如果在第V-1次迭代后，还能继续松弛，则说明有负权环
            //因为最短路最多有E-1条边
            printf("图中包含负权环，无法求解最短路径。\n");
            free(dist);
            return;
        }
    }

    // 打印最短路径
    printf("顶点\t距离源点的最短路径\n");
    for (int i = 0; i < V; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }

    free(dist);
}
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void WeightedNegative( Table T )
{
    Queue Q;
    Vertex V, W;
    Q = CreateQueue (NumVertex );  
    MakeEmpty( Q );
    Enqueue( S, Q ); /*Enqueue the source vertex*/
    while ( !IsEmpty( Q ) ) 
    {
        V = Dequeue( Q );
        for ( each W adjacent to V )
        if ( T[ V ].Dist + Cvw < T[ W ].Dist ) 
        {
            T[ W ].Dist = T[ V ].Dist + Cvw;
            T[ W ].Path = V;
            if ( W is not already in Q )
                Enqueue( W, Q );
        } /*end-if update*/
    } /*end-while */
    DisposeQueue( Q ); /*free memory*/
}