上海市工程质量建设管理协会网站,北京设计制作网站制作,买域名自己做网站,app设计ppt对于一张有向图#xff0c;我们一般有邻接矩阵和邻接表两种存储方式。对于无向图#xff0c;可以把无向边看作两条方向相反的有向边#xff0c;从而采用与有向图一样的存储方式。 $$ 邻接矩阵的空间复杂度为 O(n^2)#xff0c;因此我们一般不采用这种方式 $$ 我们用数组模… 对于一张有向图我们一般有邻接矩阵和邻接表两种存储方式。对于无向图可以把无向边看作两条方向相反的有向边从而采用与有向图一样的存储方式。 $$ 邻接矩阵的空间复杂度为 O(n^2)因此我们一般不采用这种方式 $$ 我们用数组模拟链表长度为n的表头数组head记录了从每个节点出发的第一条边在 ver 和 edge 数组中的存储位置长度为 m 的边集数组 ver 和 edge 记录了每条边的终点和边权。长度为 m 的数组 next 模拟了链表指针表示从相同节点出发的下一条边在 ver 和 edge数组中的存储位置。 $$ 邻接表的空间复杂度为 O(n m) $$
void add(int x, int y, int z) {ver[tot] y, edge[tot] z, Next[tot] head[x], head[x] tot;
}//访问从 x 出发的所有边
for (int i head[x]; i; i Next[i]) {int y ver[i], z edge[i];//找到了一条有向边(x, y),权值为 z
}
单源最短路径 单源最短路径问题(Single Source Shortest PsthSSSP问题) 是说给定一张有向图 G (VE)V是点集E是边集|V| n|E| m节点以 [1,n] 之间的连续整数编号(xyz) 描述一条从 x 出发到达 y长度为 z 的有向边。设 1 号点为起点求长度为 n 的数组 dist其中dist[i]表示从起点 1 到 节点 i 的最短路径的长度。 Dijkstra算法 $$ Dijkstra算法的流程如下: $$ $$ 1.初始化 dist[1] 0其余节点的 dist 值为正无穷大 $$ $$ 2.找出一个未被标记的、dist[x] 最小的节点 x然后标记节点 x $$ $$ 3.扫描节点 x 的所有出边 (xyz)若 dist[y] dist[x] z则使用 dist[x] z 更新 dist[y] $$ $$ 4.重复上述 2 ~ 3 两个步骤直到所有节点都被标记 $$ Dijkstra 算法基于贪心思想它只适用于所有边的长度都是非负数的图。当边长都是非负数时全局最小值不可能再被其他节点更新故在第一步中选出的节点 x 必然满足dist[x] 已经是起点到 x 的最短路径。我们不断选择全局最小值进行标记和扩展最终可得到起点 1 到每个节点的最短路径的长度。 const int N 1e3 10;
int a[N][N], d[N], n, m, s;
bool v[N];
void dijkstra(int s) {std::memset(d, 0x3f, sizeof d);d[s] 0;for (int i 1; i n; i) {//重复进行 n - 1次int x 0;//找到未标记节点中 dist 最小的for (int j 1; j n; j) {if (!v[i] (x 0 || d[j] d[x])) {x j;}}v[x] 1;//用全局最小值点 x 更新其他节点for (int y 1; y n; y) {d[y] std::min(d[y], d[x] a[x][y]);}}
}int main() {std::cin n m s;//构建邻接矩阵std::memset(a, 0x3f, sizeof a);for (int i 1; i n; i) {a[i][i] 0;}for (int i 1; i m; i) {int u, v, w;std::cin u v w;a[u][v] std::min(a[u][v], w);}//求单源最短路径dijkstra(s);for (int i 1; i n; i) {std::cout d[i] \n[i n];}return 0;
} $$ 上面程序的时间复杂度为O(n^2)$$ $$ 主要瓶颈在于第一步的寻找全局最小值的过程 $$
$$ 可以用二叉堆(C STL priority_queue) 对 dist 数组进行维护 $$
$$ 用 O(logn) 的时间获取最小值并从堆中删除 $$
$$ 用O(logn) 的时间执行一条边的扩展和更新 $$
$$ 最终可在 O((m n)logn) 的时间内实现 Dijkstra 算法 $$
const int N 1e5 10, M 1e6 10;
int head[N], ver[M], edge[M], next[M], d[N];
bool v[N];
int n, m, s, tot;
std::priority_queuestd::pairint, int q;void add(int u, int v, int w) {ver[tot] v, edge[tot] w, next[tot] head[u], head[u] tot;
}void dijkstra(int s) {std::memset(d, 0x3f, sizeof d);d[s] 0;q.push(std::make_pair(0, s));while (q.size()) {//取出栈顶int x q.top().second;q.pop();if (v[x]) continue;v[x] true;//扫描所有出边for (int i head[x]; i; i next[i]) {int y ver[i], z edge[i];if (d[y] d[x] z) {//更新,把新的二元组插入堆d[y] d[x] z;q.push(std::make_pair(-d[y], y));}}}
}int main() {std::cin n m s;//构建邻接表for (int i 1; i m; i) {int u, v, w;add(u, v, w);}dijkstra(s);for (int i 1; i n; i) {std::cout d[i] \n[i n];}return 0;
}
Bellman - Ford 算法和 SPFA 算法 $$ 给定一张有向图若对于图中的某一条边 (x, y, z)有 dist[y] \le dist[x] z 成立 $$
$$ 则称该边满足三角形不等式。 $$
$$ 若所有边都满足三角形不等式则 dist 数组就是所求最短路 $$
$$ 下面介绍SPFA算法 $$
const int N 1e5 10, M 1e6 10;
int head[N], ver[M], edge[M], next[M], d[N];
int n, m, tot, s;
std::queueint q;
bool v[N];void add(int u, int v, int w) {ver[tot] v, edge[tot] w, next[tot] head[u], head[u] tot;
}void spfa(int s) {std::memset(d, 0x3f, sizeof d);d[s] 0, v[s] true;q.push(s);while (q.size()) {//取出对头int x q.front();q.pop();v[x] false;//扫描所有出边for (int i head[x]; i; i next[i]) {int y ver[i], z edge[i];if (d[y] d[x] z) {//更新,把新的二元组插入堆d[y] d[x] z;if (!v[y]) {q.push(y), v[y] true;}}}}
}
