dijkstra写法
邻接矩阵
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define r read()
const int maxn = 1e4;
const int INF = 0x3f3f3f3f;
int n,m,q;
int G[maxn][maxn];
bool vis[maxn];/// 标记位
int close[maxn];///最近距离所在的终点
int dis[maxn];///最近的距离
void out(int x)
{
if(x==q){cout<<x<<' ';return ;}
out(close[x]);
cout<<x<<' ';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(G,INF,sizeof(G));/// 按照逻辑含义 不存在的边的长度为无穷大 但是边相同的会被覆盖
memset(vis,false,sizeof (vis));
memset(close,-1,sizeof(close));
///freopen("1.txt","r",stdin);
///freopen("2.txt","w",stdout);
cin>>m>>n>>q;///n条边 m个顶点
for (int i=0;i<n;++i)
{
int u;
int v;
int w;
cin>>u>>v>>w;
G[u][v] = w;
}
for (int i=1;i<=m;++i)
{
dis[i] = G[q][i];/// 首次更新 确立v1为永久点
if (!vis[i] && dis[i]!=INF) close[i] = q;/// 和当前永久点相连最近
}
int idx = q;
vis[q] = true;
dis[q] = 0;
for (int i=1;i<m;++i)
{
int mine = INF;
for (int k=1;k<=m;++k)
{
if(!vis[k]&&dis[k]<mine)
{
mine = dis[k];
idx = k;
}
} /// 找出当前的最小临时点 设为永久点
vis[idx] = true;/// 设为永久点 进行标记
/// cout<<close[idx]<<' '<<idx<<endl;
for (int j=1;j<=m;++j)
{
if (!vis[j]&&dis[idx]+G[idx][j] < dis[j])/// 更新永久点相连的顶点
{
close[j] = idx;
//sum -= dis[j];
dis[j] = dis[idx]+G[idx][j];
//sum += dis[j];
}
}
}
/*for (int i=1;i<=m;++i)
{
cout<<close[i]<<' ';
}*/
///puts("");
out(m);
return 0;
}
/*
dijkstra算法 本种写法针对于无重边的情况 ，主要采用的思想是贪心
每次利用上一次得到的永久点进行更新
首先将起始点设为永久点 然后对于和永久点相连的边进行更新 更新最短的距离dis[i]
然后对于剩余的临时点查找其中的最小值设为新的永久点 用当前的永久点进行更新
如此往复 每次更新到当前最近的距离的顶点 对于记录vq到所有点的最短路径，进行回溯
*/
邻接表写法
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define r read()
const int maxn = 1e4;
const int INF = 0x3f3f3f3f;
int n,m,q;
bool vis[maxn];
int dis[maxn];/// 储存从开始位置当当前下标节点的最短距离
int close[maxn]; ///储存最短距离最近的顶点编号
struct vex_edge /// 头节点结构
{
struct edge_Node *first_Node;/// 储存第一个边节点
}G[maxn];
struct edge_Node
{
int idx;/// 跟G[i]-idx 表示 从i到idx的边
int weight;/// 权重
struct edge_Node * next_edge;/// 下一个边节点
};
void out(int x)
{
if(x==q){cout<<x<<' ';return ;}
out(close[x]);
cout<<x<<' ';/// 逆序输出
}
void init()/// 初始化
{
memset(vis,false,sizeof(vis));
memset(close,-1,sizeof(close));
memset(dis,INF,sizeof(dis));
for (int i=1;i<=m;++i) G[i].first_Node = NULL;/// 头节点首先为空 此时是不存在的头节点 只是一个指针
/// 有需要也可以自行弄一个头节点
}
signed main()
{
cin>>m>>n>>q;/// n条边 m个节点 q是开始出发的起点
init();/// 初始化
for (int i=1;i<=n;++i)
{
int u,v,w;
cin>>u>>v>>w;
struct edge_Node*p;
p = (edge_Node*)malloc(sizeof(edge_Node));
p->idx = v;
p->weight = w;
p-> next_edge = G[u].first_Node; /// 插入操作 将所有的链节点放到p之后
G[u].first_Node = p;
}
/*
for (int i=1;i<=m;++i)
{
struct edge_Node *op;
op = G[i].first_Node;
cout<<i<<' ';
while (op!=NULL)
{
cout<<op->idx<<' '<<op->weight<<' ';
op = op ->next_edge; G[q].first_Node;
}
cout<<endl;
}
*/
struct edge_Node *op;
op = G[q].first_Node;
while (op != NULL) /// 找出跟q相连的边节点
{
dis[op->idx] = op->weight;
close[op->idx] = q;
///cout<<op->weight<<endl;
op = op ->next_edge;
}
int id = q;
vis[q] = true;
dis[q] = 0; ///
close[q] = q;/// 最后回溯路径的基础条件
for (int i=1;i<m;++i)
{
int mine = INF;
for (int k=1;k<=m;++k)
{
if(!vis[k]&&dis[k]<mine)
{
mine = dis[k];
id = k;
}
} /// 找出当前的最小临时点 设为永久点
vis[id] = true;/// 设为永久点 进行标记
///cout<<id<<endl;
/// cout<<close[idx]<<' '<<idx<<endl;
struct edge_Node *T;
T = G[id].first_Node;
while (T!=NULL)
{
if (!vis[T->idx]&&dis[T->idx] > (dis[id]+(T->weight)))
{
close[T->idx] = id;
dis[T->idx] = dis[id] +T->weight;
/// cout<<T->idx<<' '<<dis[T->idx]<<endl;
}
T = T->next_edge;
}
}
for (int i=1;i<=m;++i)
cout<<close[i]<<' ';
puts("");
for (int j=1;j<=m;++j) out(j),puts("");/// 输出每一条最短路径
return 0;
}
堆优化
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define r read()
const int maxn = 1e6+7;
const int INF = INT_MAX;
int n,m,q;
struct Node{
int v;
int c;
Node(int vv=0,int cc=0):v(vv),c(cc){}
bool operator <(const Node &res)const {
return c>res.c;
}/// 堆顶为小 小根堆
};
struct Edge{
int v,weight;/// 到当前节点的最短距离
Edge(int vv=0,int cc=0):v(vv),weight(cc){}
};
vector<Edge> G[maxn];
bool vis[maxn];
int dis[maxn];
void Dijkstra(int start)
{
memset(vis,false,sizeof(vis));
for (int i=1;i<=m;++i)dis[i] = INF;
priority_queue<Node>que;
while (!que.empty()) que.pop();///清除
dis[start] = 0;
que.push(Node(start,0));/// 插入
Node tmp;
while (!que.empty())
{
tmp = que.top();
que.pop();
int u = tmp.v;///找到当前永久点的编号
if (vis[u]) continue;
vis[u] = true;
for (int i=0;i<G[u].size();++i)
{
int v = G[tmp.v][i].v;///和永久点相连的其他点
int weig = G[u][i].weight;///永久点到其他顶点的距离
if (!vis[v] && dis[v]>dis[u]+weig)///更新
{
dis[v] = dis[u] + weig;
que.push(Node (v,dis[v]));///记录
}
}
}
}
void insert_edge(int u,int v,int w)
{
G[u].push_back(Edge(v,w));
}
signed main()
{
cin>>m>>n>>q;
///for(int i=1;i<=m;i++)G[i].clear();
for (int i=1;i<=n;++i)
{
int u,v,w;
cin>>u>>v>>w;
insert_edge(u,v,w);
}
Dijkstra(q);
for (int i=1;i<=m;++i) cout<<dis[i]<<' ';
puts("");
return 0;
}