算法－最短路径_最短路径 作者 李曲 c++ pta 以最短的时间为依维卡提供所有披萨。

图的最短路径问题是一个经典的计算机科学和运筹学问题，旨在找到图中两个顶点之间的最短路径。这种问题在多种场景中都有应用，如网络路由、地图导航等。

解决图的最短路径问题有多种算法，其中最著名的包括：
1.迪杰斯特拉算法
(1). 图的要求
适用于权重非负的图。
(2). 实现
该算法的实现通常包括以下步骤：
a. 初始化：将源节点标记为最短路径已经知道．设置其路径距离为0．将其入队列．
b. 循环迭代，直到队列为空
b.1. 出队列，得p．
b.2.迭代&更新．
即对从p可达，且最短路径尚未确定节点q．
比较，若p的路径距离+Edge<p,q>小于q的路径距离，则更新q的路径距离=p的路径距离+Edge<p,q>．设置p为其路径上一节点．
b.3.从最短路径尚未确定节点中选出路径值最小节点t．将t的最短路径标记为已经知道．t入队列．在无法选出这样的t时，表示剩余节点均不可达．可提前结束迭代．

(3). 实例

(4). 算法实现

#define MAX 0x7fffffff
class NodeInfo{
public:
    char m_nName;
    int32_t m_nPath = MAX;
    int32_t m_nPreIndex = -1;
    int32_t m_nTag = -1;
};

template<class T>
class Node{
public:
    T m_nEle;
};

template<class EdgeInfo>
class Edge{
public:
    int32_t m_nWeight = MAX;
    bool m_bValid = false;
};

Node<NodeInfo> stNodes[7];
Edge<int> stEdges[7][7];
void Sort(void* lpBegin, void *lpEnd);
int main(){
    stNodes[0].m_nEle.m_nName = 'A';
    stNodes[1].m_nEle.m_nName = 'B';
    stNodes[2].m_nEle.m_nName = 'C';
    stNodes[3].m_nEle.m_nName = 'D';
    stNodes[4].m_nEle.m_nName = 'E';
    stNodes[5].m_nEle.m_nName = 'F';
    stNodes[6].m_nEle.m_nName = 'G';
    
    stEdges[0][1].m_nWeight = 1;
    stEdges[0][1].m_bValid = true;
    stEdges[1][0].m_bValid = true;
    stEdges[1][0].m_nWeight = 1;

    stEdges[0][4].m_bValid = true;
    stEdges[0][4].m_nWeight = 2;

    stEdges[4][1].m_bValid = true;
    stEdges[4][1].m_nWeight = 2;

    stEdges[1][3].m_bValid = true;
    stEdges[1][3].m_nWeight = 1;

    stEdges[1][5].m_bValid = true;
    stEdges[1][5].m_nWeight = 4;
    stEdges[4][3].m_bValid = true;
    stEdges[4][3].m_nWeight = 2;
    stEdges[3][2].m_bValid = true;
    stEdges[3][2].m_nWeight = 1;
    stEdges[3][6].m_bValid = true;
    stEdges[3][6].m_nWeight = 2;
    stEdges[2][6].m_bValid = true;
    stEdges[2][6].m_nWeight = 2;
    
    int nSourceIndex = 0;
    stNodes[nSourceIndex].m_nEle.m_nTag = 1;
    stNodes[nSourceIndex].m_nEle.m_nPath = 0;
    stNodes[nSourceIndex].m_nEle.m_nPreIndex = -1;

    int32_t nArrQueue[7];
    int32_t nFirst = 0;
    int32_t nEnd = 0;
    int32_t nNum = 0;
    nArrQueue[0] = nSourceIndex;
    nFirst = 0;
    nEnd = 1;
    nNum = 1;
    while(nNum > 0){
        // 出队列
        int32_t nIndex;
        if(nNum = 1){
            nIndex = nArrQueue[nFirst];
            nFirst = 0;
            nEnd = 0;
            nNum = 0;
        }
        else{
            nIndex = nArrQueue[nFirst];
            nFirst = (nFirst+1)%7;
            nNum--;
        }

        // 迭代&更新
        for(int32_t i = 0; i < 7; i++){
            if(stEdges[nIndex][i].m_bValid && stNodes[i].m_nEle.m_nTag == -1){
                if(stNodes[i].m_nEle.m_nPath > stNodes[nIndex].m_nEle.m_nPath + stEdges[nIndex][i].m_nWeight){
                    stNodes[i].m_nEle.m_nPath = stNodes[nIndex].m_nEle.m_nPath + stEdges[nIndex][i].m_nWeight;
                    stNodes[i].m_nEle.m_nPreIndex = nIndex;
                }
            }
        }

        // 入队列
        // 选择未访问节点中最短距离最小的一个
        nIndex = -1;
        int32_t nMin = MAX;
        for(int32_t i = 0; i < 7; i++){
            if(stNodes[i].m_nEle.m_nTag == -1 && stNodes[i].m_nEle.m_nPath < nMin){
                nMin = stNodes[i].m_nEle.m_nPath;
                nIndex = i;
            }
        }
        if(nIndex == -1){
            break;// 所有节点均已被访问．或剩余节点全部不可达．
        }
        // 选举的节点就是最短路径已知的
        stNodes[nIndex].m_nEle.m_nTag = 1;
        if(nNum == 0){
            nArrQueue[0] = nIndex;
            nFirst = 0;
            nEnd = 1;
            nNum++;
        }
        else{
            nArrQueue[nEnd] = nIndex;
            nEnd = (nEnd+1)%7;
            nNum++;
        }
    }

    // test
    printf("finish\n");
    while(true){
        int32_t nIndex = -1;
        scanf("%d", &nIndex);
        getchar();
        printf("path_%d\n", stNodes[nIndex].m_nEle.m_nPath);
        printf("%c ", stNodes[nIndex].m_nEle.m_nName);
        while(nIndex != -1){
            printf("%c ", stNodes[stNodes[nIndex].m_nEle.m_nPreIndex].m_nEle.m_nName);
            nIndex = stNodes[nIndex].m_nEle.m_nPreIndex;
        }
        printf("\n");
    }
    return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

2.贝尔曼-福特算法（Bellman-Ford Algorithm）：
(1). 图的要求
可以处理带有负权重的图，但无法处理包含负权重环的图。
针对权重为负的图，可以让所有边权中加上一个基础量转变为权重非负的，再通过迪杰斯特拉求解．所以，正常没必要用这个．
时间复杂度为O(|V|*|E|)。

(2). 算法
贝尔曼-福特算法（Bellman-Ford Algorithm）的实现过程可以分为以下三个阶段：

a. 初始化阶段：
创建一个数组Distant，用于记录从源点s到图中各个顶点的最短路径长度估计值。通常，将源点s到自己的距离Distant[s]初始化为0，而将源点s到其他所有顶点的距离初始化为一个较大的值（如无穷大），表示这些顶点与源点之间的最短路径尚未确定。
b. 松弛操作阶段：
这个阶段需要进行|V|-1次迭代，其中V是图中顶点的数量。在每一次迭代中，遍历图中的所有边(u, v)，并检查是否可以通过这条边来更新从源点s到顶点v的最短路径长度估计值。
具体来说，对于每一条边(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则更新Distant[v]为Distant[u] + w(u, v)。这里，w(u, v)是边(u, v)的权重，表示从顶点u到顶点v的距离或成本。
通过不断的松弛操作，Distant数组中的值会逐渐逼近从源点到各个顶点的实际最短路径长度。
c. 负权回路检测阶段：
在完成|V|-1次松弛操作后，再进行一次额外的松弛操作。这次操作的目的是为了检测图中是否存在负权回路（即从某个顶点出发，经过一系列边后回到该顶点，且整个回路的总权重为负）。
如果在额外的松弛操作中，仍然有Distant数组的值被更新，那么就说明图中存在负权回路。因为负权回路的存在会导致最短路径问题无解，因为可以通过不断绕行负权回路来减小路径长度。
如果额外的松弛操作没有更新Distant数组的值，那么算法结束，Distant数组中存储的就是从源点到各个顶点的最短路径长度。