迪杰斯特拉算法例题,随机优化算法有哪些

戴克斯特拉算法是一种用于解决两点之间最短路径的算法。 给定的图表GV，e和起点s终点t被用于求出从s到t的最短路径。

目录伪代码例题邻接矩阵未优化AC代码邻接表_优先队列优化的AC代码链正向星优先队列AC代码链正向星AC代码板问题伪代码//G为图，数组d为从源点到各点的最短路径长度，s为起点dijksttg 将for(n次循环) u=d ) u )最小化；尚未访问的顶点的标签； 记录u已被访问的for (从u出发可到达的所有顶点v ) if ) v未被访问，优化d[v] (以u为中介点使从s到顶点v的最短距离d[v]更好)； } }例题

在以下例题中编写并优化代码

P1339 [USACO09OCT]Heat Wave

相邻矩阵未优化交流码# include cstdio # includealgorithmusingnamespacestd； 常数上限=2501； 常数上限=6201； int G[maxn][maxn]； //0为bool isvis[maxn]； //每个点是否已经通过int ds[maxn]； //s点到各点的距离，-1表示无法到达int res的int n，m； //n个点m条边int s，t； //起点和终点的void dijkstra () for ) ) intI=1； i=n； I ) ds[i]=0x7fffffff； ds[s]=0； //ds初始化for(intk=0； kn； k () /循环k次int next=-1； //下一个要扩展的节点int ds_next=0x7fffffff； for(intI=1； i=n； I ) ) /优化点1if (is vis [ I ]==false ds [ I ] ds _ next ) {next=i； ds_next=ds[i]； }if(next==-1 ) return； //此时，此连通图中的所有点已访问isvis[next]=true； 进行到next，标记已访问的if (next==t ) ) /如果是终点，则保持res=ds_next； 返回； }for(intI=1； i=n； I ()/ds ) /优化点2if(g[next][I]！=0isvis[I]==false(/I点未通过ds[I]=min(ds[I]，ds_nextg[next] ) ) )。 }}}int main () scanf ) ' %d%d%d '，n，m，s，t )； int x，y； for(intI=0； im； I )扫描(' % d % d )、x、y )； scanf('%d '，G[x][y]； G[y][x]=G[x][y]； (}dijkstra )； printf('%d '，res )； 返回0； }这个代码有两个可以优化的地方

在优化点1处，如果每次查找最小的未访问ds[]数组时使用优先级队列，则无需从头到尾扫描ds[]数组的优化点2，而是在查找相邻节点并更新ds[]数组时使用相邻矩阵可以修改为旁边的桌子或链条前方型。

因此，优化的代码如下：相邻表_优先队列优化的AC代码# include iostream # include vector # includequeueusingnamespacestd； 类型支付int，int pp； 结构节点{ int t； //目标节点int w； //边缘权node(}node(intt，int w ) :t(t ) t )，w ) {}； 常数上限=2501； 常数上限=6201； 向量向量节点(max n1； //使用动态数组相邻表bool isvis[maxn]； //每个点是否已经通过int ds[maxn]； //s点到各点的距离，-1表示无法到达int res的int n，m； //n个点m条边int s，t； //起点和终点的void dijkstra () for ) ) intI=1； i=n； I ) ds[i]=0x7fffffff； ds[s]=0； priority_queuepp、vectorpp、greaterpp pq； //在小天花板上安装pq.push(make_pair(0，s )； PTP； //tp.first最近距离，tp.second节点while (！ pq.empty () ) {tp=pq.top； pq.pop (； int u=tp.second； //当前节点int d=tp.first； //距当前节点的开始节点的距离if(u==t ) {res=d； 返回； }if(isvis[u] ) continue； //此点已被isvis[u]=true访问； for(intI=0； iG[u].size (； I () in

t v = G[u][i].t;//u->v 有边if(isvis[v]==false&&d+G[u][i].w<ds[v]){//i点尚未访问,并且以u为中介可以使得到i点的距离更小ds[v] = d+G[u][i].w;pq.push(pp(ds[v],v));}}}}int main(){cin>>n>>m>>s>>t;int x,y,z;for(int i=0;i<m;i++){cin>>x>>y>>z;G[x].push_back(node(y,z));G[y].push_back(node(x,z));}dijkstra();cout<<res;return 0;} 链式前向星+优先队列AC代码 链式前向星

链式前向星是一种边集数组,类似邻接表但是比邻接表用起来简单方便。
数据结构如下:

struct node{int t;//目标结点 int w;//边权 int next;//下一个邻点 }edge[maxm];int cnt = 1;//当前有cnt-1个边int head[maxn]={0};//每个顶点的邻边void addedge(int u,int v,int w){//添加边 edge[cnt].t = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;} 解释:head[1]表示"结点1"的第一条边的edge数组编号,如果是0则表示"结点1"没有相邻的边,否则edge[head[1]]表示的是第一条相邻边的信息,next是下一个与"结点1"相邻的边，添加边的时候类似邻接表的头插法。 AC代码 #include<cstdio>#include<iostream>#include<queue>using namespace std;const int maxn = 2501;//点数 const int maxm = 13001;//边数 struct node{int t;//目标结点 int w;//边权 int next;//下一个邻点 }edge[maxm];int cnt = 1;//当前有cnt-1个边int head[maxn]={0};//每个顶点的邻边void addedge(int u,int v,int w){//添加边u->v edge[cnt].t = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;} bool visit[maxn] = {false};int ds[maxn];int n,m,s,t;//n个点,m条边,s是起点,t是终点 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;//优先级是first距离(小顶堆)//first距离,second结点编号1-n.使用结构体也行,需要重载小于号或者比较函数 int res;void dijkstra(){for(int i=1;i<=n;i++)ds[i] = 0x7fffffff;//距离矩阵初始化ds[s] = 0;pq.push(make_pair(0,s)); while(!pq.empty()){pair<int,int> p = pq.top();pq.pop();int u = p.second;//当前结点 int d = p.first;//当前结点距离开始结点的距离if(u==t){res = d;break;}if(visit[u]) continue;visit[u]=true;//更新visitfor(int i=head[u];i!=0;i=edge[i].next){int v = edge[i].t;int w = edge[i].w;if(visit[v]==false&&d+w<ds[v]){ds[v] = d+w;pq.push(make_pair(d+w,v));}} }return;}int main(){scanf("%d %d %d %d",&n,&m,&s,&t);int u,v,w;for(int i=0;i<m;i++){scanf("%d %d %d",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}dijkstra();printf("%d",res);return 0;} 板子题

【模板】单源最短路径（弱化版）