做网站放广告收益,北京最新进出京政策(今天),大二网页设计作业,建筑工程网络教育DS图—图的最短路径/Dijkstra算法【数据结构】
题目描述 给出一个图的邻接矩阵#xff0c;输入顶点v#xff0c;用迪杰斯特拉算法求顶点v到其它顶点的最短路径。
输入 第一行输入t#xff0c;表示有t个测试实例
第二行输入顶点数n和n个顶点信息
第三行起#xff0c;每行…DS图—图的最短路径/Dijkstra算法【数据结构】
题目描述 给出一个图的邻接矩阵输入顶点v用迪杰斯特拉算法求顶点v到其它顶点的最短路径。
输入 第一行输入t表示有t个测试实例
第二行输入顶点数n和n个顶点信息
第三行起每行输入邻接矩阵的一行以此类推输入n行
第i个结点与其它结点如果相连则为距离无连接则为0数据之间用空格隔开。
第四行输入一个顶点v表示求该顶点v到其他顶点的最短路径距离
以此类推输入下一个示例
输出 对每组测试数据输出 每行输出顶点v到某个顶点的最短距离和最短路径
每行格式顶点v编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出顶点v编号-其他顶点编号–1。具体请参考示范数据
输入样例1 2 5 0 1 2 3 4 0 5 0 7 15 0 0 5 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 6 V0 V1 V2 V3 V4 V5 0 0 10 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0 V0
输出样例1 0-1-5----[0 1 ] 0-2-9----[0 3 2 ] 0-3-7----[0 3 ] 0-4-10----[0 3 2 4 ] V0-V1–1 V0-V2-10----[V0 V2 ] V0-V3-50----[V0 V4 V3 ] V0-V4-30----[V0 V4 ] V0-V5-60----[V0 V4 V3 V5 ]
Dijkstra算法
思路
取一个点称为原点求该点到其他所有点的最短路径。先取一个点在集合中比较该点到其他任意一个点的最短路径将该点加入集合更新原点到不在集合中的点的路径是否可以更换为经过新加的点再到该点如!果更短就更换再重复这个过程 #includebits/stdc.h
using namespace std;
int main()
{int t;cint;for(int i 0; i t; i){int n;cinn;//记录节点string s[205];//记录路径 不记录起点和终点string arr[205] {};//记录节点所在下标mapstring,int m;for(int j 0; j n; j) {cins[j];m[s[j]] j;}//邻接矩阵int a[205][205] {0};for(int j 0; j n; j){for(int k 0; k n; k) cina[j][k];}string v;cinv;int start m[v];//记录是否加入集合中即是否已计算最短路径int visited[205] {0};visited[start] 1;while(1){//找到最短路径并记录int flag -1;int small 99999999;for(int j 0; j n; j){if(!visited[j] a[start][j] a[start][j] small){small a[start][j];flag j;}}//全部找完 退出if(flag -1) break;visited[flag] 1;//更新经过新加的点的最短路径for(int j 0; j n; j){if(!visited[j] a[flag][j] (a[start][j] 0 || a[start][j] a[start][flag] a[flag][j])){a[start][j] a[start][flag] a[flag][j];//路径记录arr[j] arr[flag] s[flag] ;}}}for(int j 0; j n; j){if(j ! start){if(a[start][j]) {if(arr[j] ) printf(%s-%s-%d----[%s %s ]\n,v.c_str(),s[j].c_str(),a[start][j],v.c_str(),s[j].c_str());else printf(%s-%s-%d----[%s %s%s ]\n,v.c_str(),s[j].c_str(),a[start][j],v.c_str(),arr[j].c_str(),s[j].c_str());}else printf(%s-%s--1\n,v.c_str(),s[j].c_str());}}}return 0;
}
