目录
一、基础
二、使用链式前向星+每次遍历的第一次优化
前向星:
链式前向星:
1、结构
2、存储边
3、遍历
第一次优化代码
三、堆优化
主要思想:
数据类型:
四、完整代码
一、基础
直接用邻接矩阵,每次遍历查找来进行操作
void dijkstra()
{
//初始化
//dist
//vis[]存储是否标记
for(int i=1;i<=n;i++){
dist[i]=inf;//先将所有的dist置为inf
vis[i]=false;//将所有点都置为未标记状态
}
dist[beg]=0;//起始点为dist值为0
for(int i=1;i<n;i++){
int k=-1;
int Min=inf;
for(int i=1;i<=n;i++){//每次遍历找出此时未被标记且最小的dist对应的点
if(!vis[i]&&dist[i]<Min){
Min=dist[i];
k=i;
}
}
if(k==-1){//如果找完了跳出即可
break;
}
vis[k]=true;//这个点标记
for(int i=1;i<=n;i++){//通过找出的这个点进行松弛操作
if(!vis[i]&&dist[k]+cost[k][i]<dist[i]){
dist[i]=dist[k]+cost[k][i];
}
}
}
}
二、使用链式前向星+每次遍历的第一次优化
讲解过多次依然经常忘……希望这是我最后一次搜它
前向星:
将输入的边排序:先按起点序号顺序排序,若起点相同,再按终点序号顺序排列
链式前向星:
不需要对边进行排序,直接存储,节省了排序时间
1、结构
1、结构体数组edge[i],用来存储第i条边;
struct edge{
int next;//下一条边的存储位置,edge[i].next表示与第i条边同起点的下一条边的存储位置,
int to;//该边的终点
int w;//该边的权值
};
2、head[i]数组用来存储以i为起点的第一条边在edge中的下标;head数组一般初始化为-1
2、存储边
void add(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
3、遍历
for(int i=head[u];1!=0;i=edge[i].next)
第一次优化代码
void dijkstra()
{
for(int i=1;i<=n;i++){
dist[i]=inf;
vis[i]=false;
}
dist[1]=0;
for(int i=1;i<n;i++){
int k=-1;
int Min=inf;
for(int i=1;i<=n;i++){
if(!vis[i]&&dist[i]<Min){
Min=dist[i];
k=i;
}
}
if(k==-1){
break;
}
vis[k]=true;
//只是这儿有所变动
//邻接表,读取以k开头的每条边
for(int i=head[k];i!=-1;i=edges[i].next){
int to=edges[i].v;
if(!vis[to]&&dist[k]+edges[i].w<dist[to]){
dist[to]=dist[k]+edges[i].w;
}
}
}
}
三、堆优化
主要思想:
使用一个优先队列来代替最短距离的查找,因为优先队列每次弹出的元素一定是整个队列中的最大元素。
数据类型:
priority_queue<pair<int,int> >q;
四、完整代码
#include <iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
struct EDGE{
int next;//下一条边的存储位置
int to;//该边的终点
int w;//该边的权值
}edge[10005];
int cnt;
int n,m;
bool visit[1005];
int dist[1005];
int head[10005];
void add(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void dijkstra(){
priority_queue<pair<int,int> > q;
for(int i=1;i<=n;i++){
dist[i]=inf;
visit[i]=false;
}
dist[1]=0;
q.push(make_pair(0,1));// 赋值<0,1> 代表 顶点1,距离为0
while(!q.empty()){
pair<int,int> t;
t=q.top();
q.pop();
int u=t.second; // u为该条路径的终点
visit[u]=true;
for(int j=head[u];j!=-1;j=edge[j].next){
int v=edge[j].to;
if(visit[v])
continue;
if(dist[v]>dist[u]+edge[j].w){
dist[v]=dist[u]+edge[j].w;
q.push(make_pair(dist[v]*(-1),v));//默认优先级比较从大到小,所以乘-1
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0)
break;
memset(head,-1,sizeof(head));
cnt=0;
int u,v,w;
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dijkstra();
printf("%d\n",dist[n]);
}
return 0;
}