基层建设期刊上什么网站查询文章,网站开发帐务处理,电脑上两个版本的wordpress,遵义网站图的最短路径问题是一个经典的计算机科学和运筹学问题#xff0c;旨在找到图中两个顶点之间的最短路径。这种问题在多种场景中都有应用#xff0c;如网络路由、地图导航等。
解决图的最短路径问题有多种算法#xff0c;其中最著名的包括#xff1a; 1.迪杰斯特拉算法 (1).…图的最短路径问题是一个经典的计算机科学和运筹学问题旨在找到图中两个顶点之间的最短路径。这种问题在多种场景中都有应用如网络路由、地图导航等。
解决图的最短路径问题有多种算法其中最著名的包括 1.迪杰斯特拉算法 (1). 图的要求 适用于权重非负的图。 (2). 实现 该算法的实现通常包括以下步骤 a. 初始化将源节点标记为最短路径已经知道设置其路径距离为0将其入队列 b. 循环迭代直到队列为空 b.1. 出队列得p b.2.迭代更新 即对从p可达且最短路径尚未确定节点q 比较若p的路径距离Edgep,q小于q的路径距离则更新q的路径距离p的路径距离Edgep,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;
};templateclass T
class Node{
public:T m_nEle;
};templateclass EdgeInfo
class Edge{
public:int32_t m_nWeight MAX;bool m_bValid false;
};NodeNodeInfo stNodes[7];
Edgeint 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 (nFirst1)%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 (nEnd1)%7;nNum;}}// testprintf(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;
}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数组中存储的就是从源点到各个顶点的最短路径长度。
