网站弹出信息怎么做,国际贸易平台排名,大连城建设计研究院网站,网站建站专家目录 介绍#xff1a;
代码#xff1a;
结果#xff1a; 介绍#xff1a;
迪杰斯特拉算法#xff08;Dijkstras algorithm#xff09;是一种用于计算加权图的单点最短路径的算法。它是由荷兰计算机科学家Edsger W. Dijkstra在1956年发明的。
该算法的思路是#xf…目录 介绍
代码
结果 介绍
迪杰斯特拉算法Dijkstras algorithm是一种用于计算加权图的单点最短路径的算法。它是由荷兰计算机科学家Edsger W. Dijkstra在1956年发明的。
该算法的思路是从给定源点开始不断找到距离该点最近的未访问节点标记这个节点为已访问并更新与该节点相邻的节点的最短路径。通过这样不断扩大已访问节点的范围最终可以求出源点到其他所有节点的最短路径。
具体实现时可以使用一个优先队列来保存即将访问的节点优先队列中的元素按照节点与源点的距离从小到大排序每次取出距离最小的节点进行访问。
迪杰斯特拉算法的复杂度为O(E log V)其中E为边的数量V为节点的数量。虽然该算法是一个贪心算法并不能保证一定找到最优解但对于大多数实际应用场景而言其效率和正确性都已经得到了充分的验证。 代码
#includeiostream
using namespace std;
int G[100][100], n, maxint999, min1, v;
int s[100],d[100],path[100];//集合s代表已经找到最短路径的点
void DIJ(int v0)//迪杰斯特拉算法,从v0点到任意点的最短路径
{for (int i 0; i n; i)//初始化{s[i] 0;//视为空集d[i] G[v0][i];//初始最短路径为v0到个点的权值if (d[i] maxint)//v0与i之间有弧则前驱设为v0path[i] v0;else//v0与i之间无弧则前驱设为-1path[i] -1;}s[v0] 1;//将v0加入集合sd[v0] 0;//源点到源点距离为0for (int i 1; i n; i)//访问剩下的n-1个点{min1 maxint;for (int j 0; j n; j){if (!s[j] d[j] min1)//点不在集合s内且小于最小边{v j;//选择一条当前最短路径终点为vmin1 d[j];}}s[v] 1;//将v加入集合sfor (int j 0; j n; j)//将v加入集合后更新从v0到剩余点的最短路{if (!s[j] (d[v] G[v][j]) d[j])//该点不在集合s内且加入v点后最短路径小于之前的最短路径{d[j] d[v] G[v][j];//更新最短路径path[j] v;//前驱设为v}}}for (int i 1; i n; i)//访问各点的最短路径{int t path[i];cout i 点的最短路径i ;while (t ! -1){cout t ;t path[t];}cout 最短路径长度d[i];cout endl;}
}
int main()
{cout 输入顶点数 endl;cin n;for (int i 0; i n; i)for (int j 0; j n; j)G[i][j] maxint;cout 输入边数 endl;int e;cin e;cout 输入边 endl;for (int i 1; i e; i){int v1, v2, w;cin v1 v2 w;G[v1][v2] w;}DIJ(0);//从0号点到任意点的最短路径
}
结果
