adjacency matrix
Let a graph have $n $points, then the adjacency matrix of the graph is a matrix of $n * n $.
So a two-dimensional array $map [] [] $is used to store the adjacency matrix.
For example, if you know that the path weight from $x $to $y $in an undirected graph is $z $, you can assign $map[x][y] $to $z $. Because it is an undirected graph, you need to connect the edges in reverse, that is, assign $map[y][x] $to $z $.
The spatial complexity of adjacency matrix is $O(n ^ 2) $.
Adjacency table
The spatial complexity of adjacency matrix is too wasteful for sparse graph, so adjacency table is useful.
Adjacency tables are usually stored in four arrays $head [] $, $ver [] $, $edge [] $, $next [] $.
The $head [] $array records the storage position of the first edge of each node in the $ver $array and $edge $array;
The $ver [] $array and $edge [] $array store the end point and edge weight of each edge respectively;
$next [] $array simulates a linked list pointer;
//Add a directed edge from x to y with a weight of z
void add (int x, int y, int z) {
ver[++ tot] = y;
edge[tot] = z;
next[tot] = head[x];
head[x] = tot;
}
//Access all edges from x
for (int i = head[x]; i; i = next[i]) {
int y = ver[i], z = edge[i];
}
The spatial complexity of adjacency table is $O(n + m) $.
Dijkstra
Basics
Dijkstra algorithm is to find the shortest path of a single source. A single source means that you can only know the shortest distance from a point to all other points.
Algorithm flow: find the unmarked point closest to the source point every time, then start from this point, update the distance from all edge points of this point to the source point, and repeat this operation until all nodes are marked.
Next, let's look at the code:
void dijkstra (int s) { //s is our source
memset(dis, INF, sizeof(dis)); //We initialize the distance from all points to the source point to infinity
int cur = s; //cur is the current node and initialized as the source point
dis[cur] = 0;
vis[cur] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++)
if (!vis[j] && dis[cur] + map[cur][j] < dis[j]) //At this time, a better path that can reach the next point from cur and is not marked is found, so this path is updated
dis[j] = dis[cur] + map[cur][j];
int mini = INF;
for (int j = 1; j <= n; j ++)
if (!vis[j] && dis[j] < mini) //At this point, the shortest and unmarked point that can be reached is found
mini = dis[cur = j]; //Update our starting point for the next time
vis[cur] = 1; //Mark our next starting point
}
}
optimization
The time complexity of the last program is $O(n ^ 2) $, so how to optimize it?
Is it found that every time we find the next starting point, we are looking for it by violence? If the priority queue is used to maintain the nearest point, we can use $O(\log n) $to find the point.
At the same time, we can also change the adjacency matrix into adjacency table to optimize the spatial complexity.
The code is as follows:
struct Point {
int id, val; //id is the number of the node, and val is the path from the source point to the node
Point (int id, int val) : id(id), val(val) {}
bool operator < (const Point &a) const { //overload operators
return val > a.val;
}
};
void dijkstra (int s) {
for (int i = 1; i <= n; i ++)
dis[i] = INF;
priority_queue <Point> q;
q.push(Point(s, 0));
dis[s] = 0;
while (!q.empty()) {
int x = q.top().id; //Use the priority queue to find our next target node cur
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = next[i]) { //Adjacency table traversal
int y = ver[i];
if (!vis[y] && dis[y] > dis[x] + edge[i]) {
dis[y] = dis[x] + edge[i];
q.push(Point(y, dis[y]));
}
}
}
}
So let's write one Template question Practice your hands!
Although the time complexity of Dijkstra algorithm is superior, it can not run for graphs with negative weight edges.
Because Dijkstra is based on the greedy idea, it only takes the shortest path each time, and the node cannot be changed after being marked. However, if there is a negative weight edge, the greedy idea is wrong.
Then for graphs with negative weight edges, SPFA algorithm can solve this problem.
SPFA
Given a directed graph, if an edge in the graph satisfies $dis[x] + z ≥ dis[y] $($x $, $y $represents the nodes at both ends, and $z $represents the weight), it is said that the edge satisfies the triangular inequality.
If all edges satisfy the triangle inequality, then the $dis [] $array is the shortest path.
SPFA algorithm makes all edges satisfy triangle inequality.
Algorithm flow: establish a queue and put the source point into the queue. Every time you take out the team head from the queue, starting from this point, if his edge makes $dis [x] + Z < dis [y] $, put the edge point into the queue, and then pop up the team head. Repeat until the queue is empty.
The code is as follows:
void spfa (int s) {
for (int i = 1; i <= n; i ++)
dis[i] = INF;
queue <int> q;
q.push(s);
dis[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = next[i]) {
int y = ver[i];
if (dis[y] > dis[x] + edge[i]) {
dis[y] = dis[x] + edge[i];
if (!vis[y]) {
q.push(y);
vis[y] = 1;
}
}
}
}
}
Floyd
floyd algorithm is different from the above two algorithms in that it seeks the multi-source shortest path. Its essence is dynamic programming, which defines $dis_{i, j} $is the shortest path from $I $to $J $, with an initial value of $dis_{i, j} = a_{i, j} $, $a $are adjacency matrices.
State transition equation $dis_ {I, J} = min (DIS {I, J}, dis {I, K} + dis {K, J}) $, $k $is the city along the way.
The code is also very simple:
for (int k = 1; k <= n; k ++) for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
It is worth noting that $k $must be placed in the outermost loop.
Because $k $is a phase, if it is placed in the innermost loop, $dis[i][j] $will be determined after this $n $loop, but in this $n $loop, $dis[i][k] $and $dis[k][j] $are not necessarily the shortest circuit.
If placed in the outermost loop, $dis[i][j] $is always updated.
Then there is Template question Yes.
test questions
T2: Tigger home
T3: Optimal trade
Problem solution
Repair circuit:
The four points around each grid can be regarded as a node, and the number of nodes $n = (r + 1) * (c + 1) $.
If in the box at position $(ri, ci) $:
Point in the upper left corner: $(ri - 1) * (c + 1) + ci $;
Point in the upper right corner: $(ri - 1) * (c + 1) + ci + 1 $;
Point in the lower left corner: $ri * (c + 1) + ci $;
Point in the lower right corner: $ri * (c + 1) + ci + 1 $;
So you can show all the points.
Connect the points in the upper left corner and the lower right corner of the circuit of \ with a $0 $edge weight, and the points in the lower left corner and the upper right corner with a $1 $edge weight, representing a $1 $cost.
Similarly, the circuits of / are connected in the same way.
Finally, the minimum cost can be found by running the shortest path with Dijkstra algorithm.
code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 300010;
int n, t, r, c, tot, head[N], ver[N << 2], edge[N << 2], nex[N << 2], vis[N], dis[N];
struct Point {
int id, vel;
Point (int id, int vel) : id(id), vel(vel) {}
bool operator < (const Point &a) const {
return vel > a.vel;
}
};
inline void add (int x, int y, int z) {
ver[++ tot] = y;
edge[tot] = z;
nex[tot] = head[x];
head[x] = tot;
}
void dijkstra (int x) {
for (int i = 1; i <= n; i ++)
dis[i] = 0x3f3f3f3f;
priority_queue <Point> q;
q.push(Point(x, 0));
dis[x] = 0;
while (!q.empty()) {
int cur = q.top().id;
q.pop();
if (vis[cur]) continue;
vis[cur] = 1;
for (int i = head[cur]; i; i = nex[i]) {
int id = ver[i];
if (!vis[id] && dis[id] > dis[cur] + edge[i]) {
dis[id] = dis[cur] + edge[i];
q.push(Point(id, dis[id]));
}
}
}
}
int main () {
scanf("%d", &t);
while (t --) {
memset(head, 0, sizeof(head));
memset(ver, 0, sizeof(ver));
memset(edge, 0, sizeof(edge));
memset(nex, 0, sizeof(nex));
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
tot = 0;
scanf("%d%d", &r, &c);
n = (r + 1) * (c + 1);
for (int i = 1; i <= r; i ++) {
char s[N];
scanf("%s", s + 1);
for (int j = 1; j <= c; j ++) {
if (s[j] == '\\') {
add((i - 1) * (c + 1) + j, i * (c + 1) + j + 1, 0);
add(i * (c + 1) + j + 1, (i - 1) * (c + 1) + j, 0);
add((i - 1) * (c + 1) + j + 1, i * (c + 1) + j, 1);
add(i * (c + 1) + j, (i - 1) * (c + 1) + j + 1, 1);
} else {
add((i - 1) * (c + 1) + j + 1, i * (c + 1) + j, 0);
add(i * (c + 1) + j, (i - 1) * (c + 1) + j + 1, 0);
add((i - 1) * (c + 1) + j, i * (c + 1) + j + 1, 1);
add(i * (c + 1) + j + 1, (i - 1) * (c + 1) + j, 1);
}
}
}
if ((r + c) % 2) {
printf("NO SOLUTION\n");
continue;
}
dijkstra(1);
printf("%d\n", dis[(r + 1) * (c + 1)]);
}
return 0;
}
Tigger home:
Compared with the shortest path template, this problem has more ways to limit its use.
Let $dis[i][j] $represent the shortest path from the source point to the $I $node, using $j $times to limit the road.
Suppose we go from $x $node to $y $node and use $j $times to restrict the road:
If the current road is an ordinary road, $dis[y][j] = min(dis[x][j] + edge[x][y], dis[y][j]) $;
If you are on a restricted road, $dis[y][j + 1] = min(dis[x][j] + edge[x][y], dis[y][j]) $.
Finally, the answer is to find the minimum $dis[n][j] $on the premise that the number of roads is limited to $j ≤ k $.
code:
#include <cstdio>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e8;
const int MAXN = 510;
const int MAXM = 2010;
int n, m, q, k, ans, dis[MAXN][MAXN];
struct data {
int u, j;
};
struct edge {
int to, w, d;
};
vector <edge> e[MAXN];
inline int read () {
int res = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9') {
res = res * 10 + (ch - '0');
ch = getchar();
}
return res;
}
void spfa () {
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= k; j ++)
dis[i][j] = INF;
dis[1][0] = 0;
queue <data> q;
q.push((data){1, 0});
while (!q.empty()) {
int u = q.front().u, j = q.front().j;
q.pop();
for (int i = 0; i < e[u].size(); i ++) {
int v = e[u][i].to, w = e[u][i].w, d = e[u][i].d;
if (d) {
if (dis[v][j + 1] > dis[u][j] + w) {
dis[v][j + 1] = dis[u][j] + w;
q.push((data){v, j + 1});
}
}
else {
if (dis[v][j] > dis[u][j] + w) {
dis[v][j] = dis[u][j] + w;
q.push((data){v, j});
}
}
}
}
}
int main () {
n = read();
m = read();
q = read();
k = read();
k = min(k, min(n, q));
for (int i = 1; i <= m; i ++) {
int u, v, w;
u = read();
v = read();
w = read();
e[u].push_back((edge){v, w, 0});
}
for (int i = 1; i <= q; i ++) {
int u, v, w;
u = read();
v = read();
w = read();
e[u].push_back((edge){v, w, 1});
}
spfa();
ans = INF;
for (int i = 0; i <= k; i ++)
ans = min(ans, dis[n][i]);
if (ans == INF)
ans = -1;
printf("%d\n", ans);
return 0;
}
Optimal trade:
The problem requires us to buy and sell crystal balls with the best price difference on the way from node $1 $to node $n $.
We might as well define a $minn [] $array, $minn[x] $represents the route from node $1 $to node $n $, and node $x $can be bought at the lowest price of $minn[x] $before.
The initial value of the $minn [] $array is the price of the crystal ball of the node. If we go from the $x $node to the $y $node, $minn[y] = min(minn[y], minn[x]) $.
Therefore, we can update the $minn [] $array when we use SPFA to walk this picture.
Define another $f [] $array, $f[x] $represents the highest price difference obtained before walking to the $x $node.
If we go from $x $node to $y $node, it is obvious that $f[y] $can be transferred as follows: $f[y] = max(f[x], a[y] - minn[y]) $($a[y] $represents the crystal ball price of $y $node).
Since it must end at the $n $node, $f[n] $is the answer.
code:
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 100010, M = 500010;
int n, m, a[N], head[N], ver[M << 1], nex[M << 1], tot, vis[N], minn[N], f[N];
inline void add (int x, int y) {
ver[++ tot] = y;
nex[tot] = head[x];
head[x] = tot;
}
inline void spfa () {
queue<int> q;
vis[1] = 1;
q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nex[i]) {
int y = ver[i];
minn[y] = min(minn[y], minn[x]);
if (a[y] - minn[y] > f[y] || f[x] > f[y]) {
f[y] = max(a[y] - minn[y], f[x]);
if (!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
}
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) {
f[i] = -1;
scanf("%d", &a[i]);
minn[i] = a[i];
}
f[1] = 0;
for (int i = 1; i <= m; i ++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (z == 1)
add(x, y);
else {
add(x, y);
add(y, x);
}
}
spfa();
printf("%d", f[n]);
return 0;
}