使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

这篇具有很好参考价值的文章主要介绍了使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原理:

Dijkstra算法是解决**单源最短路径**问题的**贪心算法**

它先求出长度最短的一条路径,再参照该最短路径求出长度次短的一条路径

    直到求出从源点到其他各个顶点的最短路径。

首先假定源点为u,顶点集合V被划分为两部分:集合 S 和 V-S。 初始时S中仅含有源点u,其中S中的顶点到源点的最短路径已经确定。

集合S 和V-S中所包含的顶点到源点的最短路径的长度待定,称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径,

并用dist[]记录当前每个顶点对应的最短特殊路径长度。

选择特殊路径长度最短的路径,将其连接的V-S中的顶点加入到集合S中,同时更新数组dist[]。一旦S包含了所有顶点,dist[]就是从源到所有其他顶点的最短路径长度。

(1)数据结构。 设置地图的带权邻接矩阵为map[][],即如果从源点u到顶点i有边,就令map[u][i]=<u,i>的权值,否则map[u][i]=∞;

              采用一维数组dist[i]来记录从源点到i顶点的最短路径长度:采用一维数组p[i]来记录最短路径上i顶点的前驱。

(2)初始化。令集合S={u},对于集合V-S中的所有顶点x,初始化dist[i]=map[u][i],如果源点u到顶点i有边相连,初始化p[i]=u(i的前驱是u),否则p[i]=-1

(3)找最小。在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t,即dist[t]=min,则顶点t就是集合V-S中距离源点u最近的顶点。

(4)加入S战队。将顶点t加入集合S,同时更新V-S

(5)判结束。如果集合V-S为空,算法结束,否则转6

(6)借东风。在(3)中已近找到了源点到t的最短路径,那么对集合V-S中所有与顶点t相邻的顶点j,都可以借助t走捷径。

            如果dist[j]>dist[t]+map[t][j],则dist[j]=dist[t]+map[t][j],记录顶点j的前驱为t,p[j]=t,转(3)。

            //我自己在这里理解就是,从u找到与它最近的点t,在从t找到与它最近的点j,在....按照这样持续下去,直到最后一个点

    这里我再通俗的解释下这个借东风的意思。

    源点为1,如果我们找到了距离源点最近的点2,且点2与3,4相连。

        这样,我们如果要倒3,4有两种方法:

                1->2->3(4)

                1->3(4)

        这里我们就要判断是从1直接到3(4)快,还是经过2后快。假设<1,2>=2 / <2,3>=3 / <1,3>=4

            根据上面的数据,我们第一次找最小找到的是2结点,如果我们直接把2替换掉1当做源点继续找下一个最近的点,这种方法是错的。

            因为可以看出1->3只用4,而过2的话要用5。

实现代码如下:

#include<bits/stdc++.h>
#include<omp.h>
#include<time.h>
using namespace std;//1899 20296
const int N=2000;	//城市个数可修改
const int INF=1e7;	//初始化无穷大为.......
int G[N][N],dist[N],p[N],n,m;	//n为城市个数,m为城市间路线的条数
bool flag[N];	//如果flag[i]=true,说明该顶点i已经加入到集合S;否则i属于集合V-S
//#pragma omp parallel for

void Dijkstra(int u){
    #pragma omp parallel for
	for(int i=1;i<=n;i++){//********>>>--1--<<<******//
        
		dist[i]=G[u][i];	//初始化源点u到其他各个顶点的最短路径长度
		flag[i]=false;
		if(dist[i]==INF)
			p[i]=-1;	//说明源点u到顶点i无边相连,设置p[i]=-1
		else
			p[i]=u;	//说明源点u到顶点i有边相连,设置p[i]=u
	}
	flag[u]=true;//初始化集合S中,只有一个元素:源点u
	dist[u]=0;	//初始化源点u的最短路径为0,自己到自己的最短路径




   
	for(int i=1;i<=n;i++){//********>>>--2--<<<******//
		int temp=INF,t=u;

        #pragma omp parallel for
		for(int j=1;j<=n;j++){//>>--3--<<在集合V-S中寻找距离源点u最近的顶点t
			if(!flag[j] && dist[j]<temp){
				t=j;	//记录距离源点u最近的顶点
				temp=dist[j];
			}
		}

		if(t==u) return ;	//找不到t跳出循环
		flag[t]=true;	//否则,将t加入集合S

        #pragma omp parallel for
		for(int j=1;j<=n;j++){//>>--4--<<更新集合V-S中与t邻接的顶点到u的距离
			if(!flag[j] && G[t][j]<INF){//!flag[j]表示j在v-s集合中,map[t][j]<INF表示t与j邻接
				if(dist[j]>(dist[t]+G[t][j])){//经过t到达j的路径更短
					dist[j]=dist[t]+G[t][j];
					p[j]=t;	//记录j的前驱为t
				}
			}
		}	
	}	
}


void findpath(int u)
{
	int x;
	stack<int>s;
	cout << "源点为:" << u << endl;
	for (int i = 1; i <= n; i++)
	{
		x = p[i];
		while (x != -1)
		{
			s.push(x);
			x = p[x];
		}
		cout << "源点到其他各顶点的最短路径为:";
		while (!s.empty())
		{
			cout << s.top() << "--";
			s.pop();
		}
		cout << i << ";最短距离为:" << dist[i] << endl;
	}
}



int main(int argc, char *argv[]){
	int u, v, w, start;
    int number = atoi(argv[1]);   //线程数
    ifstream fin("input.txt");

    fin >> n >> m;
    for(int i=1;i<=n;i++)//初始化图的邻接矩阵
		for (int j = 1; j <= n; j++)
		{
			G[i][j] = INF;//初始化邻接矩阵为无穷大
		}
    while(fin>>u >> v >> w)
    {
        G[u][v] = min(G[u][v], w);	//邻接矩阵存储,保留最小的距离
    }

	cout << "请输所在的位置:" << endl;
	cin>>start;
	double st, ed;
    omp_set_num_threads(number);   //设置线程数
    st = omp_get_wtime();
	Dijkstra(start);
	ed = omp_get_wtime();
	findpath(start);
	cout << "Time: " << ed-st<< "s" << endl;
	return 0;
}

使用 #pragma omp parallel for进行加速:

编译:g++ ./filename.cpp -o ./filename -fopenmp

运行: ./filename n  n表示线程数

运行结果:

使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

数据长这样:

使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

 也可以用这一组数据来测试:

6 9
0 1 7
0 2 9
0 5 14
1 2 10
1 3 15
2 3 11
2 5 2
3 4 6
4 5 9

 数据集下载提取码:k3v2

OpenMP基本概念
OpenMP是一种用于共享内存并行系统的多线程程序设计方案,支持的编程语言包括C、C++和Fortran。OpenMP提供了对并行算法的高层抽象描述,特别适合在多核CPU机器上的并行程序设计。编译器根据程序中添加的pragma指令,自动将程序并行处理,使用OpenMP降低了并行编程的难度和复杂度。当编译器不支持OpenMP时,程序会退化成普通(串行)程序。程序中已有的OpenMP指令不会影响程序的正常编译运行。

在VS中启用OpenMP很简单,很多主流的编译环境都内置了OpenMP。在项目上右键->属性->配置属性->C/C++->语言->OpenMP支持,选择“是”即可。

OpenMP执行模式
OpenMP采用fork-join的执行模式。开始的时候只存在一个主线程,当需要进行并行计算的时候,派生出若干个分支线程来执行并行任务。当并行代码执行完成之后,分支线程会合,并把控制流程交给单独的主线程。

一个典型的fork-join执行模型的示意图如下:

OpenMP编程模型以线程为基础,通过编译制导指令制导并行化,有三种编程要素可以实现并行化控制,他们分别是编译制导、API函数集和环境变量。

编译制导
编译制导指令以#pragma omp 开始,后边跟具体的功能指令,格式如:#pragma omp 指令[子句[,子句] …]。常用的功能指令如下:

parallel:用在一个结构块之前,表示这段代码将被多个线程并行执行;
for:用于for循环语句之前,表示将循环计算任务分配到多个线程中并行执行,以实现任务分担,必须由编程人员自己保证每次循环之间无数据相关性;
parallel for:parallel和for指令的结合,也是用在for循环语句之前,表示for循环体的代码将被多个线程并行执行,它同时具有并行域的产生和任务分担两个功能;
sections:用在可被并行执行的代码段之前,用于实现多个结构块语句的任务分担,可并行执行的代码段各自用section指令标出(注意区分sections和section);
parallel sections:parallel和sections两个语句的结合,类似于parallel for;
single:用在并行域内,表示一段只被单个线程执行的代码;
critical:用在一段代码临界区之前,保证每次只有一个OpenMP线程进入;
flush:保证各个OpenMP线程的数据影像的一致性;
barrier:用于并行域内代码的线程同步,线程执行到barrier时要停下等待,直到所有线程都执行到barrier时才继续往下执行;
atomic:用于指定一个数据操作需要原子性地完成;
master:用于指定一段代码由主线程执行;
threadprivate:用于指定一个或多个变量是线程专用,后面会解释线程专有和私有的区别。
相应的OpenMP子句为: 


private:指定一个或多个变量在每个线程中都有它自己的私有副本;
firstprivate:指定一个或多个变量在每个线程都有它自己的私有副本,并且私有变量要在进入并行域或任务分担域时,继承主线程中的同名变量的值作为初值;
lastprivate:是用来指定将线程中的一个或多个私有变量的值在并行处理结束后复制到主线程中的同名变量中,负责拷贝的线程是for或sections任务分担中的最后一个线程; 
reduction:用来指定一个或多个变量是私有的,并且在并行处理结束后这些变量要执行指定的归约运算,并将结果返回给主线程同名变量;
nowait:指出并发线程可以忽略其他制导指令暗含的路障同步;
num_threads:指定并行域内的线程的数目; 
schedule:指定for任务分担中的任务分配调度类型;
shared:指定一个或多个变量为多个线程间的共享变量;
ordered:用来指定for任务分担域内指定代码段需要按照串行循环次序执行;
copyprivate:配合single指令,将指定线程的专有变量广播到并行域内其他线程的同名变量中;
copyin:用来指定一个threadprivate类型的变量需要用主线程同名变量进行初始化;
default:用来指定并行域内的变量的使用方式,缺省是shared。
利用omp_set_num_threads()来设置线程数,

利用#pragma omp parallel sections 声明下面大括号中的语句要并行多线程执行;

利用#pragma omp section 分配线程。

看懂下列helloworld的代码对openmp并行就会有一定了解。

 
 文章来源地址https://www.toymoban.com/news/detail-498944.html

到了这里,关于使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言 最短路径 迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中单源最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最

    2024年02月03日
    浏览(44)
  • java实现迪杰斯特拉(Dijkstra)算法求解最短路问题

    迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是寻找从一个顶点到其余各顶点的最短路径算法,可用来解决最短路径问题。 迪杰斯特拉算法采用贪心算法的策略,将所有顶点分为已标记点和未标记点两个集合,从起始点开始,不断在未标记点中寻

    2024年02月12日
    浏览(41)
  • 【数据结构】图解:迪杰斯特拉算法(Dijkstra)最短路径

    目录 一、方法描述 二、例题一  ​编辑 三、例题二  有图如上,用迪杰斯特拉算法求顶点A到其余各顶点的最短路径,请问1.第一步求出的最短路径是A到C的最短路径2.第二步求出的是顶点A到顶点B/F的最短路径3.顶点A到D的最短路径长度是__25___ (填数字)4.顶点A到顶点F的最短路

    2024年02月12日
    浏览(37)
  • DS图—图的最短路径(无框架)迪杰斯特拉算法

    目录 题目描述 AC代码 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起,每行输入邻接矩阵的一行,以此类推输入n行 第i个结点与其它结点如果

    2023年04月08日
    浏览(41)
  • MATLAB轻松绘制地图路线——Dijkstra(迪杰斯特拉)算法最短路径规划

    利用MATLAB绘制地图需要三个基本数据: 节点 节点坐标 节点间相通的路线 以11B交通巡警平台调度问题中的A区数据为例: (数据及工程文件下载链接见文末) Demo1: 可通过已知节点的坐标,计算出各节点之间的距离,有Matlab基础的同学可以尝试Demo2, 也可通过Excel自行实现;

    2023年04月21日
    浏览(49)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(39)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(52)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(39)
  • 迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径

    迪杰斯特拉算法(Dijkstra\\\'s Algorithm),又称为狄克斯特拉算法,是一种用于解决带权重有向图或无向图最短路径问题的算法。该算法由荷兰计算机科学家艾兹赫尔·狄克斯特拉在1956年发明,是一种广泛应用于网络路由和其他领域的算法。 在 2001 年的一次采访中,Dijkstra 博士透露

    2024年02月03日
    浏览(48)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包