本文主要是介绍dijsttra 邻接表+优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dijstra原理：
以单源开始，每次以新的点去更新所有的（没访问过的点） 到单源的最短路。
其中新的点---------应该找每次更新后当前到单源权值最小的点.
作法一：邻接矩阵
void DIJ(int n)//传入顶点个数n，默认0为起点
{ int i,j,k; low[0]=0; bool flag[SIZE]={0}; flag[0]=1; for(i=1;i<n;i++) { low[i]=a[0][i]; } for(i=1;i<n;i++) { int min=INF; for(j=0;j<n;j++) { if(flag[j]==0&&low[j]<min) { min=low[j]; k=j; } } flag[k]=1; for(j=0;j<n;j++) { if(flag[j]==0&&a[k][j]+low[k]<low[j]) low[j]=low[k]+a[k][j]; } }
}作法2：邻接表+优先队列
题为：求一个点到 三个点距离和 最小的点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 5050
#define M 20010
#define INF 0x1f1f1f1f
int lowa[N],lowb[N],lowc[N];
int head[N]; //邻接表的头。下标为每个城市编号，映射是以它为顶点的第一条边 在arc中的存储位置。
struct Arc
{int next;int point;int cost;
}arc[M]; //模拟链表存储，下标是存储地址，每个节点保存末端顶点编号，与这条边权值。
struct str //优先队列的元素：保存这一点的编号 和到单源的最短路。
{int num;int cost;str(int a,int b):num(a),cost(b){}str(){}friend bool operator<(str a ,str b){return a.cost>b.cost;}
};
int vis[N];
void dij(int src,int n,int *low)
{memset(vis,0,sizeof(vis));//每个单源开始都把vis归0；priority_queue<str> q; q.push(str(src,0)); //把单源push进去，它到单源路径为0;int kk=0; while(kk<n&&!q.empty())//只要其余n-1个点都访问完，就ok了.{str s=q.top();q.pop();if(vis[s.num]) continue;//一定要防止再次访问 已经确定最短路的点。vis[s.num]=1;//标记访问了。low[s.num]=s.cost;//标志着 这一点到单源的最短路已经确定.kk++;for(int e=head[s.num];e!=-1;e=arc[e].next){if(!vis[arc[e].point])q.push(str(arc[e].point,arc[e].cost+s.cost));}}
}
int main()
{int ces=1;int n,m;int A,B,C;while(~scanf("%d%d",&n,&m)){memset(lowa,0x1f,sizeof(lowa));memset(lowb,0x1f,sizeof(lowa));memset(lowc,0x1f,sizeof(lowc));memset(head,-1,sizeof(head));scanf("%d%d%d",&C,&A,&B);for(int i=1;i<=m;i++){int x,y,k;scanf("%d%d%d",&x,&y,&k);arc[i].next=head[x];arc[i].point=y;arc[i].cost=k;head[x]=i;arc[m+i].next=head[y];arc[m+i].point=x;arc[m+i].cost=k;head[y]=m+i;}int ans=INF;dij(A,n,lowa); //用3个点做单源。dij(B,n,lowb);dij(C,n,lowc); printf("Scenario #%d\n",ces++);if(lowc[A]>=INF||lowc[B]>=INF) //图不连通.A或B到不了C{printf("Can not reah!\n");continue;}for(int i=1;i<=n;i++) //枚举Y 形交叉路的交叉点--找到最适合的两人分开的交叉点。{if(lowa[i]+lowb[i]+lowc[i]<ans){ans=lowa[i]+lowb[i]+lowc[i];}}printf("%d\n",ans);printf("\n");}return 0;
}
这篇关于dijsttra 邻接表+优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
