网站开发工作如何,便宜自适应网站建设厂家,可以看的网站都有哪些,做网站老师目录 1 基础知识2 模板3 工程化 1 基础知识
朴素版dijkstra算法的关键步骤#xff1a;
初始化d[1]0#xff0c;d[2~n]正无穷#xff0c;例如0x3f3f3f3f。用集合S来表示当前已被确定最小距离的结点们。遍历每一个结点#xff1a;找到不在S中的且距离结点1最近的结点#… 目录 1 基础知识2 模板3 工程化 1 基础知识
朴素版dijkstra算法的关键步骤
初始化d[1]0d[2~n]正无穷例如0x3f3f3f3f。用集合S来表示当前已被确定最小距离的结点们。遍历每一个结点找到不在S中的且距离结点1最近的结点记为t。将结点t加入到集合S中。看看结点t可以走到哪儿假设可以走到x比较dist[x]和dist[t] edge[t][x]如果前者大于后者则用后者去更新前者。d[1~n]即为结点1到结点x的最短距离x取1~n的值。
朴素版的dijkstra算法的核心是贪心一直找最近的最终的结果就是最近的。
2 模板
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i n - 1; i ){int t -1; // 在还未确定最短路的点中寻找距离最小的点for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;// 用t更新其他点的距离for (int j 1; j n; j )dist[j] min(dist[j], dist[t] g[t][j]);st[t] true;}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}3 工程化
题目1求结点1到结点n的最短路。
#include iostream
#include cstringusing namespace std;const int N 510;
int g[N][N];
int dist[N];
bool st[N];
int n, m;int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i n; i) {//遍历每一个结点总共有n个结点需要遍历n次int t -1; //当前距离结点1最近的结点且不在集合S中for (int j 1; j n; j) {if (!st[j] (t -1 || dist[t] dist[j])) {t j;}}st[t] true; //把t加入到集合S中for (int j 1; j n; j) {//用t取更新剩余的结点if (!st[j]) {dist[j] min(dist[j], dist[t] g[t][j]);}}}if (dist[n] 0x3f3f3f3f) return -1;else return dist[n];
}int main() {cin n m;memset(g, 0x3f, sizeof g);int a, b, c;while (m--) {cin a b c;g[a][b] min(g[a][b], c);}cout dijkstra() endl;return 0;
}
