网站建设费要摊销吗,西宁市网站建设,头像设计,wordpress 视频站主题B : DS图应用–最短路径 文章目录 B : DS图应用--最短路径DescriptionInputOutputSampleInput Output 解题思路#xff1a;初始化主循环心得#xff1a; AC代码 Description
给出一个图的邻接矩阵#xff0c;再给出指定顶点v0#xff0c;求顶点v0到其他顶点的最短路径
In…B : DS图应用–最短路径 文章目录 B : DS图应用--最短路径DescriptionInputOutputSampleInput Output 解题思路初始化主循环心得 AC代码 Description
给出一个图的邻接矩阵再给出指定顶点v0求顶点v0到其他顶点的最短路径
Input
第一行输入t表示有t个测试实例 第二行输入n表示第1个图有n个结点 第三行起每行输入邻接矩阵的一行以此类推输入n行 第i个结点与其他结点如果相连则为1无连接则为0数据之间用空格隔开 第四行输入v0表示求v0到其他顶点的最短路径距离 以此类推输入下一个示例
Output
每行输出v0到某个顶点的最短距离和最短路径 每行格式v0编号-其他顶点编号—-[最短路径]具体请参考示范数据
Sample
Input
1
5
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
0Output
0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]解题思路
首先先要了解图论里面单源最短路径的实现——Dijkstra算法知道它是怎么一步步算出源点到每一个点的最短距离的可以参考这个视频【算法】最短路径查找—Dijkstra算法然后就看代码对着视频来进行解释
// Dijkstra算法实现
void Dijkstra(int start)
{memset(dis, 0x3f, sizeof(dis));memset(fixed, 0, sizeof(fixed));last[start] -1;dis[start] 0;int minDisNode, minDis;for (int i 0; i n; i){minDis INF;for (int j 0; j n; j)if (!fixed[j] dis[j] minDis)minDisNode j, minDis dis[j];fixed[minDisNode] true;for (int j 0; j n; j){if (g[minDisNode][j] ! 0 minDis g[minDisNode][j] dis[j])dis[j] minDis g[minDisNode][j], last[j] minDisNode;}}return 0;
}初始化
memset(dis, 0x3f, sizeof(dis)); // 设置所有节点到源点的初始距离为无穷大
memset(fixed, 0, sizeof(fixed)); // 初始化所有节点为未固定
last[start] -1; // 源点的上一个节点设置为-1
dis[start] 0; // 源点到自身的距离设置为0dis[]数组存储从源点到每个节点的当前最短距离。初始时除了源点到自身的距离为0外所有其他距离都设置为无穷大。fixed[]数组用于标记节点是否已经找到了从源点出发的最短路径。last[]数组用于记录到达每个节点的最短路径上的前一个节点对于源点而言没有前一个节点所以设置为-1。
主循环
for (int i 0; i n; i)
{minDis INF;for (int j 0; j n; j)if (!fixed[j] dis[j] minDis)minDisNode j, minDis dis[j];fixed[minDisNode] true;for (int j 0; j n; j){if (g[minDisNode][j] ! 0 minDis g[minDisNode][j] dis[j])dis[j] minDis g[minDisNode][j], last[j] minDisNode;}
}第一个for循环遍历所有节点寻找最短路径。内层的第一个for循环用于找到当前未固定节点中距离源点最近的节点minDisNode。fixed[minDisNode] true;将找到的最短距离节点标记为已固定。内层的第二个for循环进行“松弛操作”通过minDisNode更新其他未固定节点的最短距离。如果通过minDisNode到某个节点的距离比当前记录的距离短则更新该距离松弛操作if (g[minDisNode][j] ! 0 minDis g[minDisNode][j] dis[j])检查是否存在一条从minDisNode到j的边并且通过这条边到达j的距离是否比当前记录的距离短。如果是更新dis[j]为通过minDisNode到j的新距离并记录last[j]为minDisNode。
心得
一开始学这个算法的时候可能会想到一个环对于这个环例如一个三个节点的环现在节点一是源点懵的地方就在于我在第一个次循环之后得出节点一到节点二最短我就把节点二纳入fixed中我就有疑惑如果是一个环的话那我从节点一到节点三再到节点二为什么不是最短。现在项想明白在循环内层第一个for循环的时候就已经挑选出最短的了哪怕节点一到节点二和节点一到节点三的距离相等节点三到节点二总不可能为负数吧。
明白这个算法的原理之后后面的输出就很简单了直接上代码吧。
AC代码
#include iostream
#include vector
using namespace std;const int INF 999999; // 定义无穷大常量void printShortestPath(int u, const vectorint previousNodes) {if (u -1)return;printShortestPath(previousNodes[u], previousNodes);cout u ;return;
}void calculateShortestPaths(int start, const vectorvectorint graph, int n) {vectorint previousNodes(n, -1);vectorint shortestDistances(n, INF);vectorint visitedNodes(n, 0);shortestDistances[start] 0;for (int i 0; i n; i) {int minDistance INF, nearestNode -1;for (int j 0; j n; j)if (!visitedNodes[j] shortestDistances[j] minDistance){nearestNode j;minDistance shortestDistances[j];}visitedNodes[nearestNode] 1;for (int j 0; j n; j)if (graph[nearestNode][j] ! 0 minDistance graph[nearestNode][j] shortestDistances[j]){shortestDistances[j] minDistance graph[nearestNode][j];previousNodes[j] nearestNode;}}for (int i 0; i n; i) {if (i ! start) {cout start - i - shortestDistances[i];cout ----[;printShortestPath(i, previousNodes);cout ] endl;}}return;
}int main() {int t;cin t;while (t--) {int n;cin n;vectorvectorint graph(n, vectorint(n));for (int i 0; i n; i)for (int j 0; j n; j)cin graph[i][j];int sourceNode;cin sourceNode;calculateShortestPaths(sourceNode, graph, n);}return 0;
}
