Ⅰ:Dijkstra单源点最短路
1.1Dijkstra
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
int v, min_w = inf; // 记录 dist 最小的顶点编号和 dist 值
for (int j = 0; j < n; ++j) {
if (!vst[j] && dist[j] < min_w) {
min_w = dist[j];
v = j;
}
}
if (min_w == inf) { // 没有可用的顶点，算法结束，说明有顶点无法从源点到达
return false;
}
vst[v] = true; // 将顶点 v 加入集合 U 中
for (int j = p[v]; j != -1; j = e[j].next) {
// 如果和 v 相邻的顶点 x 满足 dist[v] + w(v, x) < dist[x] 则更新 dist[x]，这一般被称作“松弛”操作
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
}
}
}
return true; // 源点可以到达所有顶点，算法正常结束
}
1.2Dijkstra堆优化
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap; // 用 set 来伪实现一个小根堆，并具有映射二叉堆的功能。堆中 pair<int, int> 的 second 表示顶点下标，first 表示该顶点的 dist 值
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
min_heap.insert(make_pair(0, s));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点，说明有顶点无法从源点到达，算法结束
return false;
}
// 获取堆顶元素，并将堆顶元素从堆中删除
auto iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
// 先将对应的 pair 从堆中删除，再将更新后的 pair 插入堆
min_heap.erase(make_pair(dist[x], x));
dist[x] = dist[v] + e[j].w;
min_heap.insert(make_pair(dist[x], x));
}
}
}
return true; // 存储单源最短路的结果
}
//输出数据 最短路长度存储在dst数组中
int main(){
init();
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
insert(v,u,w);
}
dijkstra(1);
cout<<dst[n]<<endl;
return 0;
}
1.3优先队列优化dij
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
struct node {
int u;
int dist;
node(int _u, int _dist) : u(_u), dist(_dist) {}
bool operator < (const node &x) const {
return dist > x.dist;
}
}; // 记录点的结构体
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
priority_queue<node> min_heap;
dist[s] = 0;
min_heap.push(node(s, 0));
while (!min_heap.empty())
// 获取堆顶元素，并将堆顶元素从堆中删除
int v = min_heap.top().u;
min_heap.pop();
if (vst[v]) {
continue;
}
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
min_heap.push(node(x, dist[x]));
}
}
}
return true;
}
Ⅱ.SPFA求负权图最短路
2.1SPFA代码
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
//开始SPFA
bool inq[MAX_N];
int d[MAX_N]; // 如果到顶点 i 的距离是 0x3f3f3f3f，则说明不存在源点到 i 的最短路
void spfa(int s) {
memset(inq, 0, sizeof(inq));
memset(d, 0x3f, sizeof(d));
d[s] = 0;
inq[s] = true;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (d[u] + e[i].w < d[v]) {
d[v] = d[u] + e[i].w;
if (!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
}
2.2SPFA判断负环
使用一个数组(in[max_n])统计每个点入队次数，当某个点入队次数>n就是存在负环
int dis[N],in[N];
bool vis[N];
bool spfa(int u){
memset(vis,false,sizeof(vis));
vis[u] = true;
memset(dis,0x3f,sizeof(dis));
dis[u] = 0;
memset(in,0,sizeof in);
in[u] = 1;
queue<int> q;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
vis[u] = false;
for(int j=head[u];~j;j = e[j].fail){
int v = e[j].v;
int w = e[j].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
++in[v];
if(in[v] > n){
return true;
}
}
}
}
}
return false;
}
Ⅲ:floyd多源点最短路
3.1floyd模板
const int inf = 0x3f3f3f3f;
int g[MAX_N][MAX_N]; // 算法中的 G 矩阵
// 首先要初始化 g 矩阵
void init() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
g[i][j] = 0;
} else {
g[i][j] = inf;
}
}
}
}
// 插入一条带权有向边
void insert(int u, int v, int w) {
g[u][v] = w;
}
// 核心代码
void floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][k] + g[k][j] < g[i][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
}
int main(){
//输入顶点个数
//初始化
//输入邻接矩阵
}