精华内容
下载资源
问答
  • 并行最短路径算法Dijkstra。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
  • 并行的Dijkstra算法要解决的问题代码段1.生成矩阵模块2.主程序模块3.输入模块实验分析 要解决的问题 代码段 1.生成矩阵模块 #include "stdafx.h" #include <stdlib.h> #include <time.h> #include <...

    要解决的问题

    在这里插入图片描述

    代码段

    1.生成矩阵模块

    #include "stdafx.h"
    #include <stdlib.h>
    #include <time.h>
    #include <fstream.h>
    #define Size 2000
    
    int aMatrix[Size][Size];
    
    int createMatrix()
    {
    	int i,j;
    	srand(time(NULL));
    	fstream fs;
    	fs.open("Matrix2000.txt",ios::out);
    	for(i=0;i<Size;i++)
    	{
    		for(j=0;j<Size;j++)
    		{
    			if(i==j)
    			{
    				aMatrix[i][j]=0;
    			}
    			else
    			{
    				aMatrix[i][j]=30+rand()%71;//1+rand()%100;
    			}
    		}
    	}
    	for(i=0;i<Size;i++)
    	{
    		for(j=0;j<i;j++)
    		{
    			aMatrix[i][j]=aMatrix[j][i];
    		}
    	}
    	for(i=0;i<Size;i++)
    	{
    		for(j=0;j<Size;j++)
    		{
    			fs<<aMatrix[i][j]<<' ';
    		}
    	}
    	fs.close();
    	return 1;
    }
    
    int main(int argc, char* argv[])
    {
    	createMatrix();
    	printf("OK!\n");	
    	return 0;
    }
    
    
    

    2.主程序模块

    #include <fstream.h>
    #include <windows.h>
    #include <stdio.h>
    #include <process.h>
    #include <string.h>
    #include "stdafx.h"
    #include <stdlib.h>
    #include <time.h>
    
    
    #define Size 2000
    #define Threadnum 10//×î´óÏß³ÌÊý ÓÃÓÚ³õʼ»¯
    #define Inf 1000000 
    
    int xcs;//Óû§ÊäÈëµÄÏß³ÌÊý
    int c1,c2;//c1,c2״̬
    
    HANDLE hMutex;
    struct ProcParam {
    	int qidian;//ÿ´ÎÕÒµÄÆðµã
    	int zhongdian;//ÿ´ÎÕÒµÄ×îºóÒ»¸öÊý
    	int threadid;//Ïß³Ìid
    	int *qbook;//´«bookÊý×éµÄÖ¸Õë
    	int *qdst;//´«dstÊý×éµÄÖ¸Õë
    	int *qmin;//´«jubuminµÄÖ¸Õë
    	int pos;//¼Ç¼×îСֵµÄ×ø±ê
    	int *qroute;//´«Â·¾¶routeÊý×éµÄÖ¸Õë
    	int condition;//
    	int *qtm;//
    };
    
    
    struct ProcParam2 {
    	int start;
    	int end;
    	int sumtime;
    	int zt;
    };
    
    int **aMatrix=new int *[Size];//´´½¨¾ØÕó
    int readMatrix()
    {
    	int i,j;
    	// ´´½¨¶¯Ì¬¶þάÊý×éaMatrix
    	for(i=0;i<Size;i++)
    	{
    		aMatrix[i]=new int [Size];
    	}
    	fstream fs;
    	fs.open("Matrix2000.txt",ios::in); //´ò¿ªÎļþmatrix.txt£¬¶ÁÈëÊý¾Ý
    	for(i=0;i<Size;i++)
    	{
    		for(j=0;j<Size;j++)
    		{
    			fs>>aMatrix[i][j];
    		}
    	}
    	fs.close();
     	return 1;
    }
    
    void time_Qiu(int *qiutime)//Çóʱ¼ä
    {
    	int t=0;
    	for(int i=1;i<=xcs;i++)
    	{
    		printf("Ïß³Ì%d:¿ªÊ¼ÓÚ%d£¬½áÊøÓÚ%d,¹²ÓÃʱ¼äΪ%dms\n",i,qiutime[(i-1)*2+0],qiutime[(i-1)*2+1],qiutime[(i-1)*2+1]-qiutime[(i-1)*2+0]);
    		qiutime[(i-1)*2+1]-qiutime[(i-1)*2+0]>t?(t=qiutime[(i-1)*2+1]-qiutime[(i-1)*2+0]):t;
    	}
    	printf("T=max{");
    	for(i=1;i<=xcs;i++)
    	{
    		printf("t%d ",i);
    	}
    	printf("}=%dms\n",t);
    
    }
    
    unsigned __stdcall biJiao(void * arg)
    {
    	ProcParam *param;
    	param = (ProcParam*)arg;
    	if(param->condition==1) param->qtm[(param->threadid*2)+0]=GetTickCount();
    	int min=Inf+1;//Èç¹û³öÏÖ¶¼ÊÇÎÞÇî¡£¡£´ý¶¨
    	int pos;//ÊÇ·ñÒª¸³³õÖµ -1ÔõôÑù£¿
    	for(int j=param->qidian;j<param->zhongdian;j++)
    	{
    		if(param->qbook[j] == 0 && param->qdst[j] < min)
    		{  
    			min = param->qdst[j];  
    			pos=j;
    		}  
    	}
    	param->qmin[param->threadid]=min;
    	param->pos=pos;
    	param->qtm[(param->threadid*2)+1]=GetTickCount();
    
        return 0;
    }
    
    
    int minFind(int *book,int *dst,int dyc,int *qiutime)//dycµÚÒ»´Î
    {
    	//int xcs=Threadnum;// ·ÖÅäµÄÏ̸߳öÊý
    	int eachfind=Size/xcs;//ÿ¸öÏß³ÌËù×ö¸öÊý
    	HANDLE hThread[Threadnum]; //HANDLE³ÆΪ¾ä±ú£¬±¾ÖÊÊÇÒ»¸ö×ÊÔ´µÄID±êʶ·û
    	unsigned threadID[Threadnum];
    	ProcParam *param=new ProcParam[Threadnum];
    	int jubuMin[Threadnum];//¾Ö²¿×îСֵÊý×é
    	for(int i=0;i<xcs;i++)//Êý×é³õʼ»¯Îª×î´óÖµ¡£
    	{
    		jubuMin[i]=Inf;
    	}
    	
    	for(i=0;i<xcs;i++)
    	{
    		param[i].qtm=qiutime;
    		param[i].condition=dyc;//ÅжÏÊÇ·ñÊǵÚÒ»´Î
    		param[i].qmin=jubuMin;
    		param[i].qbook=book;
    		param[i].qdst=dst;
    		param[i].qidian=0+eachfind*i;//Æðµã
    		if(i!=xcs-1)
    		{
    			param[i].zhongdian=param[i].qidian+eachfind;//ÖÕµã
    		}
    		else
    		{
    			param[i].zhongdian=Size;
    		}
    		param[i].threadid=i;
    		hThread[i] = (HANDLE)_beginthreadex(NULL, 0, biJiao, (void*)&param[i], 0, &threadID[i]);
    	}
    	WaitForMultipleObjects(xcs,hThread,TRUE,INFINITE);//µÈ´ýËùÓоä±ú¶¼Íê³ÉÔٱȽÏÆäÖеÄ×îСֵ  ÆäÖÐÏß³ÌÊýÒªÉ趨
    	for(i=0;i<xcs;i++)
    	{
    		CloseHandle(hThread[i]);// ¹Ø±ÕÕâ¸öÏ̶߳ÔÓ¦µÄ¾ä±ú£¬ÊÍ·Å×ÊÔ´
    	}
    	int pos;//×îСֵËùÔÚµÄλÖÃ
    	int minReal=Inf;//ËùÓоֲ¿×îСֵÖеÄ×îСֵ
    	for(int j=0;j<xcs;j++)
    	{
    		if(jubuMin[j]<minReal)
    		{
    			minReal=jubuMin[j];
    			pos=param[j].pos;
    		}
    	}
    	return pos;
    }
    
    unsigned __stdcall refresh(void * arg)
    {
    	ProcParam *param;
    	param = (ProcParam*)arg;
    	for(int k=param->qidian;k<(param->zhongdian);k++)
    	{
    		if((param->qdst[k] > param->qdst[param->pos] + aMatrix[param->pos][k]) && param->qbook[k] == 0)
    		{ 
    			param->qroute[k]=param->pos;
    			param->qdst[k] = param->qdst[param->pos] + aMatrix[param->pos][k];
    			
    		}    
    	}
        return 0;
    }
    int printroute(int *route,int end,int start,int dst)
    {
    	int newroute[Size];//ÕýÐòµÄ·¾¶
    	char str[Size]="";//¼Ç¼·¾¶µÄ×Ö·û´®
    	int i=0;
    	printf("v%d->v%dµÄ×î¶Ì·¾¶ÊÇ:\n",end,start);
    	fstream fs;
    	fs.open("print.txt",ios::app);//ÒÑ×·¼Ó·½Ê½´ò¿ª£¬ÈôÊÇios::out¾Í»áÖØдtxt
    	fs<<"v"<<end<<"->"<<"v"<<start<<"×î¶Ì·¾¶ÊÇ£º"<<endl;
    	
    	while(route[end]!=-1)
    	{
    		newroute[i]=end;
    		end=route[end];
    		i++;
    	}
    	newroute[i]=end;
    	if(end!=start)  
    	{
    		i++;
    		newroute[i]=start;
    	}
    	
    
    	for(int k=0;k<=i;k++)
    	{
    		if(k==i)
    		{
    			printf("v%d\n",newroute[k]);
    			fs<<"v"<<newroute[k]<<endl;
    		}
    		else
    		{
    			printf("v%d->",newroute[k]);
    			fs<<"v"<<newroute[k]<<"->";
    		}
    	}
    	printf("¾àÀëΪ£º%d\n",dst);
    	fs<<"¾àÀëΪ£º"<<dst<<endl;
    	fs<<"      "<<endl;
    	fs.close();
    	return 1;
    }
    
    int reshuffle(int *book,int *dst,int &pos,int start,int end,int *route)//ºÃÏñÕâÀï²»ÓüÓ&
    {
    	//int xcs=Threadnum;
    	int eachfind=Size/xcs;//ÿ¸öÏß³ÌËù×öµÄ¸öÊý
    
    	HANDLE hThread[Threadnum]; //HANDLE³ÆΪ¾ä±ú£¬±¾ÖÊÊÇÒ»¸ö×ÊÔ´µÄID±êʶ·û
    	unsigned threadID[Threadnum];
    	ProcParam *param=new ProcParam[Threadnum];
    	for(int i=0;i<xcs;i++)
    	{
    		param[i].qroute=route;
    		param[i].qbook=book;
    		param[i].qdst=dst;
    		param[i].qidian=0+eachfind*i;//Æðµã
    		if(i!=xcs-1)
    		{
    			param[i].zhongdian=param[i].qidian+eachfind;//ÖÕµã
    		}
    		else
    		{
    			param[i].zhongdian=Size;
    		}
    		param[i].pos=pos;
    		param[i].threadid=i;
    		hThread[i] = (HANDLE)_beginthreadex(NULL, 0, refresh, (void*)&param[i], 0, &threadID[i]);
    	}
    	WaitForMultipleObjects(xcs,hThread,TRUE,INFINITE);//µÈ´ýËùÓоä±ú¶¼Íê³ÉÔٱȽÏÆäÖеÄ×îСֵ  ÆäÖÐÏß³ÌÊýÒªÉ趨
    	for(i=0;i<xcs;i++)
    	{
    		CloseHandle(hThread[i]);// ¹Ø±ÕÕâ¸öÏ̶߳ÔÓ¦µÄ¾ä±ú£¬ÊÍ·Å×ÊÔ´
    	}
    	return 0;
    }
    
    
    
    void dijkstra(int *book,int *dst,int start,int end,int &time,int option)//option 0´òӡ·¾¶  option1²»´òӡ·¾¶
    {
    	int qiutime[1000];//ÇóÒ»ÂÖÖеĸ÷¸ö²¿·Öʱ¼ä
    	DWORD st,et;//starttime endtime
    	st=GetTickCount();
    	int i;
    	for(i=0;i<Size;i++)
    	{
    		book[i]=0;
    		dst[i]=aMatrix[start][i];
    	}
    	printf("\n");
    	book[start]=1;
    	int route[Size];
    	for(i=0;i<Size;i++)
    	{
    		route[i]=-1;   //ÒòΪ³õʼËùÓнڵ㶼ԴÓÚstart£¬²»ÄÜÖ»ÊÇroute[start]=-1
    	}
    
    	for(i = 1; i < Size; i++)
    	{
    		int t=minFind(book,dst,i,qiutime);//×îСֵ×ø±ê
    		book[t]=1;
    		if(t==end)break;//²»ÓÃÈ«²¿±éÀúÕÒµ½¼´¿É
    		reshuffle(book,dst,t,start,end,route);//startÆðµãendÖÕµãÊÇΪÁËÇ󷾶  route¼Ç¼µÚn¸ö½ÚµãµÄÇ°Ò»¸ö½ÚµãÊÇʲô
    	}
    	et=GetTickCount();
    	time=et-st;
    	if(!option)
    	{
    		printroute(route,end,start,dst[end]);//´òӡ·¾¶ºÍ·¾¶³¤¶È
    		time_Qiu(qiutime);
    	}
    
    }
    
    int jiexi(char *a,int size,int &start,int &end)//½âÎö×Ö·û´®£¬¶ÁÈ¡ÆäÖеÄÆðµãºÍÖÕµã
    {
    	int temp=-1,d=1,t=0;//temp=-1ÓÐv0
    	for(int i=size-1;i>=0;i--)
    	{
    		if(48<=a[i]&&a[i]<=57)
    		{
    			if(48<=a[i+1]&&a[i]<=57)
    			{
    				d*=10;
    			}
    			else
    			{
    				d=1;
    				t++;
    				temp=0;
    			}
    			temp+=(a[i]-48)*d;
    		}
    		else
    		{
    			if(temp>-1)
    			{
    				if(t==1)
    				{
    					start=temp;
    					temp=-1;
    				}
    				if(t==2)
    				{
    					end=temp;
    				}
    			}
    		}
    	}
    	return 1;
    }
    
    int input(int *qi_zhong)
    {
    	FILE* f1=fopen("Input.txt","r");
    	if(!f1) return 0;
    	char buf[1024]={0};
    	int mount=0;//¼Ç¼¹²ÓжàÉÙ¸öÆðÖÕµã
    	while(!feof(f1))
    	{
    		int start,end;
    		memset(buf, 0, sizeof(buf));//Çå¿Õ»º³åÇø
    		fscanf(f1, "%s", buf);//´ÓÎļþÖжÁÈ¡Ò»¶ÎÊý¾Ý´æÈ뻺³åÇø
    		jiexi(buf,strlen(buf),start,end);
    		qi_zhong[mount++]=start;
    		qi_zhong[mount++]=end;
    	}
    	fclose(f1);	
    	return mount;
    }
    
    void thread_Time()
    {
    	for(xcs=2;xcs<11;xcs++)
    	{
    		int time,time_sum=0;
    		int qi_zhong[100];//¼Ç¼ÆðÖÕµãµÄÊý×é
    		int mount=input(qi_zhong);
    		if(mount)
    		{
    			for(int i=0;i<mount/2;i++)
    			{		
    				int book[Size];
    				int dst[Size];
    				int start=qi_zhong[2*i];
    				int end=qi_zhong[2*i+1];
    				dijkstra(book,dst,start,end,time,1);
    				time_sum+=time;
    			}
    		}
    		printf("%d¸öỊ̈߳º%dms\n",xcs,time_sum);
    		fstream fs;
    		fs.open("time.txt",ios::app);//ios::out¾Í»áÖØдtxt
    		fs<<xcs<<"¸öỊ̈߳º"<<time_sum<<endl;
    		fs.close();
    	}
    }
    
    unsigned __stdcall bXing(void * arg)
    {
    	ProcParam2 *param2;
    	param2=(ProcParam2*)arg;
    	int qi_zhong[100];//¼Ç¼ÆðÖÕµãµÄÊý×é
    	input(qi_zhong);
    	int time=0;
    	for(int i=param2->start;i<param2->end;i++)
    	{
    		int book[Size];
    		int dst[Size];
    		dijkstra(book,dst,qi_zhong[2*i],qi_zhong[2*i+1],time,0);
    		param2->sumtime+=time;
    	}
    	return 0;
    }
    void double_Find()
    {
    	HANDLE hThread[2];
    	unsigned threadID[2];
    	ProcParam2 *param2=new ProcParam2[2];
    	int qi_zhong[100];//¼Ç¼ÆðÖÕµãµÄÊý×é
    	int mount=input(qi_zhong);
    	int n=mount/2;//¼¸¶ÔÆðÖÕµã
    	int k=n/2;
    	if(readMatrix())
    	{
    		for(int i=0;i<2;i++)
    		{
    			param2[i].start=0+i*k;
    			param2[i].sumtime=0;
    			if(i!=1)
    			{
    				param2[i].end=param2[i].start+k;
    			}
    			else
    			{
    				param2[i].end=n;
    			}
    			hThread[i] = (HANDLE)_beginthreadex(NULL, 0, bXing, (void*)&param2[i], 0, &threadID[i]);
    		}
    		WaitForMultipleObjects(2,hThread,TRUE,INFINITE);
    		CloseHandle(hThread[0]);CloseHandle(hThread[1]);
    		printf("Ëã·¨¹²ÓÃ=%dms\n",param2[0].sumtime+param2[1].sumtime);
    	}
    }
    
    int chaxun()
    {
    	printf("****       ÇëÊäÈëÊ×Ä©½ÚµãºÅ         ****\n");
    	int a,b;
    	int start,end;
    	scanf("%d %d",&a,&b);
    	FILE* f1=fopen("print.txt","r");
    	if(!f1) return 0;
    	char buf[1024]={0};
    	while(!feof(f1))
    	{
    		memset(buf, 0, sizeof(buf));//Çå¿Õ»º³åÇø
    		fscanf(f1, "%s", buf);//´ÓÎļþÖжÁÈ¡Ò»¶ÎÊý¾Ý´æÈ뻺³åÇø
    		jiexi(buf,strlen(buf),start,end);
    		if(start==b&&end==a)
    		{
    			for(int i=0;i<strlen(buf);i++)
    			{
    				printf("%c",buf[i]);
    			}
    			printf("\n");
    			memset(buf, 0, sizeof(buf));//Çå¿Õ»º³åÇø
    			fscanf(f1, "%s", buf);
    			for(i=0;i<strlen(buf);i++)
    			{
    				printf("%c",buf[i]);
    			}
    			printf("\n");
    			memset(buf, 0, sizeof(buf));//Çå¿Õ»º³åÇø
    			fscanf(f1, "%s", buf);
    			for(i=0;i<strlen(buf);i++)
    			{
    				printf("%c",buf[i]);
    			}
    			printf("\n");
    			return 1;
    		}
    		
    	}
    	printf("ÕÒ²»µ½\n");
    	fclose(f1);	
    }
    
    
    void main()
    {
    	while(1)
    	{
    		printf("***************************************\n");
    		printf("****        ²âÊÔÇëÊäÈë1            ****\n");
    		printf("****        ͳ¼ÆÇëÊäÈë2            ****\n");
    		printf("****        ²éѯÇëÊäÈë3            ****\n");
    		printf("***************************************\n");
    		int option;
    		scanf("%d",&option);
    		system("cls");
    		switch(option)
    		{
    		case 1:
    			printf("***************************************\n");
    			printf("****        ÇëÊäÈëÏß³ÌÊý           ****\n");
    			printf("***************************************\n");
    			scanf("%d",&xcs);
    			double_Find();break;
    		case 2:thread_Time();break;
    		case 3:chaxun();break;
    		default:printf("ÇëÊäÈëÕýÈ·µÄÊý\n");
    		}			
    	getchar();
    	}
    }
    
    

    3.输入模块

    //input.txt
    v8->v10
    v231->v32
    v342->v1034
    v986->v128
    v86->v1234
    

    实验分析

    在这里插入图片描述

    展开全文
  • 用粒子群算法计算最短路径,一般用于车辆路径问题%------基本粒子群优化算法(Particle Swarm Optimization)----------- %------名称:基本粒子群优化算法(PSO) %------作用:求解优化问题 %------说明:全局性,...
  • 求最短路径的串行算法在互联网上应该一搜一大堆,也非常简单,几行代码搞定。.../***********在CPU中计算最短路径函数:floydWarshallCPUReference***********/ //void FloydWarshall::floydWarshallCPUReference(unsi.

    求最短路径的串行算法在互联网上应该一搜一大堆,也非常简单,几行代码搞定。但Floyd的并行算法却很难搜到,github倒是有一些,但不容易运行成功,这里对这个算法的并行化进行详细的讲解,结合论文以及实际实现。

    需要该算法的c++代码实现,请联系~~~

    前言:对Floyd的介绍

    求所有节点间的最短路径是一个基础的图问题,可以应用在生物信息学、社交网络以及交通规划。一个经典的求解方法就是Floyd-Warshal(FW)算法 5 6,它的空间复杂度是O(n^2),时间复杂度是O(n^3)。基于块的算法的提出,有效利用了当前处理器内存的分层结构 7 8 9。然后在块算法的思路基础上,出现了很多多块CPU、多块GPU以及CPU+GPU结合的算法,但它们很多都只是用于计算最短路径距离矩阵,并不得到最短路径中间节点矩阵

    下文中的名词解释:

    最短路径距离矩阵为:从节点i到节点j的最短距离;

    最短路径中间节点矩阵为:从节点i到节点j,经过节点k最近。

    1.Floyd的串行算法

    贴一下代码,理解请看其他博客。

    /***********在CPU中计算最短路径函数:floydWarshallCPUReference***********/
    //void FloydWarshall::floydWarshallCPUReference(unsigned int *pathDistanceMatrix, unsigned int *pathMatrix, const unsigned int numNodes)
    // * @param pathDistanceMatrix    输入,最短路径距离
    // * @param pathMatrix            输入,最短路径中间节点存储矩阵
    // * @param numNodes              输入,邻接矩阵节点个数
    void floydWarshallCPUReference(float *pathDistanceMatrix, int *pathMatrix, const int numNodes)
    {
        float distanceYtoX, distanceYtoK, distanceKtoX, indirectDistance;
    
        int width = numNodes;
        int yXwidth;
    
        //Floyd算法计算所有点之间的最短路径
        for (int k = 0; k < numNodes; ++k)
        {
            for (int y = 0; y < numNodes; ++y)
            {
                yXwidth = y * numNodes;
                for (int x = 0; x < numNodes; ++x)
                {
                    distanceYtoX = pathDistanceMatrix[yXwidth + x];
                    distanceYtoK = pathDistanceMatrix[yXwidth + k];
                    distanceKtoX = pathDistanceMatrix[k * width + x];
    
                    indirectDistance = distanceYtoK + distanceKtoX;
    
                    if (indirectDistance < distanceYtoX)
                    {
                        pathDistanceMatrix[yXwidth + x] = indirectDistance;
                        pathMatrix[yXwidth + x] = k;
                    }
                }
            }
        }
    };

    2.论文阅读翻译

    2.1 Blocked United Algorithm for the All-Pairs Shortest Paths Problem on Hybrid CPU-GPU Systems

    论文题目:基于块融合的在混合CPU+GPU系统中求所有节点最短路径搜索算法

    发表日期:2012年5月27日

    作者:全是来自日本会津大学(Aizu)

    第一作者的个人简历网址:https://u-aizu.ac.jp/~kazuya-m/index_en.html

    第一作者的研究门简历网址:https://www.researchgate.net/profile/Kazuya_Matsumoto

    评价:这篇文章即算最短路径距离矩阵,也算最短路径中间节点矩阵。同时发表时间相对较新,运算效率也非常不错

    结果:非常不错,30000多节点,最快速度只需要2分钟!!!

    解决的难点:

    1.邻接矩阵的矩阵规模大于GPU本身的显存;

    2.既算出最短路径距离矩阵,又算出最短路径中间节点矩阵;

    3.邻接矩阵的矩阵规模n不是block因子b的整数倍;

    算法原理:

    1.具有两个核函数。第一个核函数解决block大小的子矩阵的子问题;另一个核函数是解决矩阵间的乘法问题。

    2.为了高效利用GPU的多个内核,优化了CPU和GPU之间的通信;

    3.将原有的n*n邻接矩阵拆分为b*b的距离矩阵和中间节点矩阵(子矩阵),b是block因子。(为了简化,文中的描述默认n是b的倍数);

    4.作者提出的算法如下:每次最外围的迭代和原串行FW算法的迭代次数相同,每次K迭代被划分为4个阶段。

    阶段示例如下:

    阶段1:更新b*b的中心线block{Dkk,Ckk};

    阶段2:更新b*b的与中心线block相关的列block{DIk,CIk} (I  !=  k);

    阶段3:更新b*b的与中心线block相关的行block{Dkj,Ckj} (j  !=  k);

    阶段4:更新b*b的其他与中心线block完全无关的block{Dij,Cij}(I  !=  k)且 (j  !=  k);

    5.为了求解阶段1的问题,可以使用传统的串行FW算法或者递归地调用基于Block的FW算法;(本文用了前者的方法,加入此算法的总算法如下图所示),算法4的4-16行运行在GPU中,算法4的合并操作17-20运行在CPU中。

    6.阶段2-阶段4可以使用矩阵乘法更新,在本问题中,就是极小加代数。极小加代数的乘法和加法是分离执行的,极小加操作(MINPLUS)是运行在GPU中,矩阵加(MMA)运行在CPU中。这个操作减少了Z,C从CPU到GPU的数据传输,也就允许了CPU和GPU之间的高速通信。

    具体的实现:

    1.平台运行在单精度下;

    2.运行环境为:Ubuntu 10.04   Linux核心2.6.32-37   gcc 4.6.2  -02优化等级

    3.第一个kernel计算子APSP问题,划分减少了数据交互时间,因为D和C没有必要送给GPU。

    算法4引入了另一个新的block因子bs,block因子的大小较大地影响着kernel的运行效率。为了在阶段1引入串行FW算法,每个外层迭代开始前,GPU线程间的同步是非常必要的。这意味着bs被共享内存的大小限制着。本文将bs=64,给两个block   (Dck,ck),(Cck,ck)需要的大小(32KB=2*64^2*4字节)等于共享内存的大小。bs取的小了,就会造成性能恶化。

    4.第二个kernel计算矩阵乘法问题,本文设计了SGEMM核(单精度通用矩阵乘法) 25 26  。在此核函数中,一个基本的乘加操作Zi,j=Zi,j+Xi,k*Yk,j可以在GPU中用单FMA实现。但是在极小加核函数中,4个不同的指令才能实现这个操作。这意味着,对于相同的矩阵大小,SGEMM核函数的效率是MINPUS核函数的4倍。这四个指令是:一个加法指令,一个比较指令以及两个复制指令。

    解决问题的技巧:

    1.解决邻接矩阵的矩阵规模n不是block因子b的整数倍

               将邻接矩阵补充数据,补为block因子b的整数倍,这样会有性能的下降(进行了无用的计算)。为了避免最坏情况下的补充,即比b的整数倍多一个,需要补充b-1个行和列的数据,采用了最忧block因子的选取方法。

    n_pad=[(n+b-1)/b]*b

    上式中,n_pad为补充后的邻接矩阵的矩阵规模;n为当前邻接矩阵的矩阵规模;b为block因子;这里的数据都是整数型,因此每次计算都有取整操作

    补充的数据,邻接矩阵的值都要设为无穷大(也就是相对于正常的数据非常大的数)。

    这个计算最优block因子b的方法,本文未给出。

    2.选择另一个block因子bs的方法

    根据共享内存的大小,决定block因子bs的大小。

    如果共享内存大小为32kB,每次计算需要两个矩阵(需x2),单精度(需x4),则根据如下的公式

    32kB=2*4*n^2

    得到矩阵的规模大小,即block因子bs的大小为64.

    3.对CPU到GPU的数据传输大小进行估计

    对于算法3,Phase1.    

    有一个距离矩阵输入,一个距离矩阵和一个节点矩阵输出,即3个矩阵;

    单精度计算,因此一个数据4个字节;

    矩阵的规模为block因子b。因此数据传输大小为:

    4*3b^2

    对于Phase2和Phase3.

    有一个依赖的中心距离矩阵输入(只需要输入距离矩阵,且对其他矩阵通用);

    每行或者列,共(n/b-1)个矩阵。每个矩阵代表有一个距离矩阵输入,一个距离矩阵和一个节点矩阵输出,即3个矩阵;

    单精度计算,因此一个数据4个字节;

    矩阵的规模为block因子b。因此数据传输大小为:

    4*(b^2+3b^2(n/b-1))

    对于Phase4.

    有一个依赖的中心距离矩阵输入(只需要输入距离矩阵,且对其他矩阵通用);

    同时有行或者列,共(n/b-1)^2个矩阵。每个矩阵代表有一个距离矩阵输入,一个距离矩阵和一个节点矩阵输出,即3个矩阵;

    单精度计算,因此一个数据4个字节;

    矩阵的规模为block因子b。因此数据传输大小为:

    4*(b^2+3b^2*(n/b-1)^2)

    4.邻接矩阵的矩阵规模大于GPU本身的显存;

                原来需要传输4*3n^2个字节的数据,现在只需要4*3b^2个字节的数据,从而解决了矩阵规模大于GPU显卡的问题。同时,b越小,越能解决这个问题。

    5.算法性能的评价

                 带宽的算法为:

    BW[字节/s]=GPU峰值计算能力[Flop/s]/计算密集性[Flops/字节]

    GPU峰值计算能力是GPU的固有属性;

    计算密集性为总共的浮点数操作与数据传输大小的比值,计算方法如下:

    计算密集性=4b^3/(4*3b^2)=b/3

    因此,使用相当大的block因子b,可以隐藏数据的传输时间(hidden communication latencies).但不能无限大的增加

    block因子b的大小,以为太大就饱和了,带宽到达极限后就不怎么增加了。对文中的机器,给出的值为b=1536.

     

    完结撒花~~~~

    有什么不懂的评论区见

    需要源码的请联系购买~~~

     

     

    展开全文
  • 为设计基于固定序的 Bellman-Ford 算法在 CUDA 平台下并行优化方案,结合算法计算密集和数据密集的特点。从核函数计算层 面,提出了访存优化方法和基于固定序优化线程发散;从 CPU-GPU 传输层面,提出了基于 CUDA 流...
  • 基于矩阵实现的最短路径算法

    万次阅读 2015-11-10 20:13:32
    1.最短路径 图中最短路径是指:寻找图(由结点和路径组成的)中两结点之间的权重最小的路径。Wikipedia上最短路径(Shortest Path)的定义如下: In graph theory, the shortest path problem is the problem of ...

    1.最短路径

    图中最短路径是指:寻找图(由结点和路径组成的)中两结点之间的权重最小的路径。Wikipedia上最短路径(Shortest Path)的定义如下:

    In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

    2.传统算法

    2.1Dijkstra算法

    Dijkstra算法是目前公认的求解最短路径的算法。其算法思想是:用指定的起点作为根,生成最短路径树(Shortest Path Tree)。然后利用两个集合,一个是包含最短路径树顶点的集合sptSet,一个是不包含最短路径树的顶点集合U。算法的每一步都将从不包含最短路径树的顶点集合U中找到一个点,使得从起点到它有最短路径。参考网址: http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
    Dijkstra算法的步骤是:

    1. 创建一个集合sptSet(Shortest Path Tree Set),用来记录最短路径树中的点,并且初始化为空。如,起点到哪些点的最短路径计算完成了。
    2. 计算图中所有点的距离值,并用无穷大初始化所有距离值。但是,起点的距离值设为0.
    3. 当sptSet没有包含图中所有点时,1.从U中选取一个距离起点最小的顶点k,并加入到sptSet中(选定的距离就是v到k的最短路径长度),2.以k为中间点,若从起点到顶点u的距离(经过顶点k)比起点到顶点u的距离(不经过顶点k)短,则修改到顶点u的距离。

    2.2算法实现

    用Python实现的代码:
    import numpy as np
    from numpy.random import rand
    
    def init(dimension):
        mat = (rand(dimension, dimension) * dimension ** 2)
        mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = np.inf
        for i in range(dimension):
            mat[i, i] = 0
        return mat
    
    #A utility function to find the vertex with minimum distance value, from
    #the set of vertices not yet included in shortest path tree
    def minDistance(distances, sptSet, dimension):
        min = np.inf
        min_index = 0
        for i in range(dimension):
            if((sptSet[i] == False) and (distances[i] < min)):
                min = distances[i]
                min_index = i
        return min_index
    
    def dijkstra(graph, dimension, source = 0):
        sptSet = []
        distances = []
        
        #Initialize all distances as INFINITE and stpSet[] as false
        for i in range(dimension):
            distances.append(np.inf)
            sptSet.append(False)
        #Distance of source vertex from itself is always 0    
        distances[source] = 0
        
        #Find shortest path for all vertices
        for i in range(dimension - 1):
            #Pick the minimum distance vertex from the set of vertices not
            #yet processed. u is always equal to src in first iteration.
            u = minDistance(distances, sptSet, dimension)
            
            #Mark the picked vertex as processed
            sptSet[u] = True
            
            for j in range(dimension):
                if((not sptSet[j]) and (distances[u] + graph[u][j] < distances[j])):
                    distances[j] = distances[u] + graph[u][j]
        return distances
    if __name__ == "__main__":
        dimension = 6
        data = init(dimension)
        data1 = [[0, 7, 9, np.inf, np.inf, 14],
                 [7, 0, 10, 15, np.inf, np.inf],
                 [9, 10, 0, 11, np.inf, 2],
                 [np.inf, 15, 11, 0, 6, 0],
                 [np.inf, np.inf, np.inf, 6, 0, 9],
                 [14, np.inf, 2, np.inf, 9, 0]]
        data3 = [[0, 4, np.inf, np.inf, np.inf, np.inf, np.inf, 8, np.inf],
                [4, 0, 8, np.inf, np.inf, np.inf, np.inf, 11, np.inf],
                [np.inf, 8, 0, 7, np.inf, 4, np.inf, np.inf, 2],
                [np.inf, np.inf, 7, 0, 9, 14, np.inf, np.inf, np.inf],
                [np.inf, np.inf, np.inf, 9, 0, 10, np.inf, np.inf, np.inf],
                [np.inf, np.inf, 4, np.inf, 10, 0, 2, np.inf, np.inf],
                [np.inf, np.inf, np.inf, 14, np.inf, 2, 0, 1, 6],
                [8, 11, np.inf, np.inf, np.inf, np.inf, 1, 0, 7],
                [np.inf, np.inf, 2, np.inf, np.inf, np.inf, 6, 7, 0]]
        print(dijkstra(data1, dimension, 0))
    

    3.基于矩阵的实现算法

    3.1算法推导

    邻接矩阵的定义形式:对角线元素值为0,即结点i到结点i的最短路径长度为0;非邻结点权值为无穷大,即结点i和结点j非邻结,则邻接矩阵的(i,j)值为无穷大;邻结点权值是权重,即结点i和结点j邻结,则邻接矩阵的(i,j)值为权重,表示如下:

    而起点向量定义如下:


    列向量与邻接矩阵A(N*N)的第j列相加,然后取最小值,表示经过k条路径到达第j个结点的最短路径,公式表示如下:


    也可以写成:


    由此,可以得到通式:


    3.2算法实现

    用Python实现的算法代码:

    import numpy as np
    from numpy.random import rand
    
    def shortestPath(adjacencyMat, distances, dimension):
    for it in range(dimension):
    #    for i in range(n):
    #    distances[i] = np.min(distances + adjacencyMat[:, i])
        distances = (distances + adjacencyMat).min(axis = 0).reshape(dimension, 1)
    #    print(distances)
    return distances 
    
    #######################################################################################################
    # distances[v] = |0 if v = startVertex
    #                |np.inf otherwise
    # 
    # adjacencyMat[u, v] = |k if u -> v, and weight = k
    #                      |0 if i == j
    #                      |np.inf if u -/> v
    #######################################################################################################
    def init(dimension, startVertex):
        distances = np.zeros((dimension, 1))
        mat = (rand(dimension, dimension) * dimension)
        mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = np.inf
        for i in range(dimension):
            distances[i] = np.inf
            mat[i, i] = 0
        distances[startVertex] = 0
        return mat, distances
    
    if __name__ == "__main__":
        startVertex = 0
        dimension = 4
        adjacencyMat, distances = init(dimension, startVertex)
        adjacencyMat2 = np.array([[0,2,4,2],[np.inf,0,1,0],[3,np.inf,0,np.inf],[1,np.inf,2,0]])
        adjacencyMat3 = np.array([[ 0 , 3.08968315, np.inf , np.inf ],
                                  [ 0.21511113 , 0 , 1.52008847 , 3.66431105],
                                  [ 2.50440191 , np.inf , 0 , 3.35943021],
                                  [ 3.84022903 , np.inf , 0.5134998 , 0 ]])
        adjacencyMat4 = np.array([[0,1,2,np.inf],[1,0,2,4],[2,2,0,3],[np.inf,4,3,0]])
        result = shortestPath(adjacencyMat3, distances, dimension)
        print(result.T)

    4.评价

    基于矩阵运算实现的图算法,有以下几点优势:

    • 易于实现。利用矩阵可以仅仅通过矩阵与矩阵或矩阵与向量的运算就可以实现一些图算法。
    • 易于并行。在超大矩阵运算中,可以采用分块的方式平行处理矩阵运算。同理,也可以很容易的移植分布式上(可以参考我的博文基于Spark实现的超大矩阵运算)。
    • 效率更高。基于矩阵的图形算法更清晰突出的数据访问模式,可以很容易地优化(实验测试工作已完成)。
    • 易于理解。这个需要对离散数学或者图论有一定基础,知道每一步矩阵运算所对应的物理意义或数学意义。



    展开全文
  • 针对城市路网最短路径求解计算量庞大、实时性要求高的问题,提出了用Floyd算法为核心的MPI+OpenMP混合编程模型来解决这个问题。MPI+OpenMP混合编程提供结点内和结点间的两级并行处理,能充分利用共享存储模型和消息...
  • 全源最短路径算法-Floyd

    千次阅读 2014-10-08 21:02:03
    一、思路  求全源最短路径可以采用单源最短路径算法实现,如采用动态

    一、思路

        求全源最短路径可以采用单源最短路径算法实现,如采用贪心算法的Dijkstra,时间开销为|V|*O(E+VlgV),动态规划的Bellman-Ford, |V|*O(V pow 2 *E),还有Bellman的优化算法SPFA。但是呢,这样无疑会在时间开销上花费昂贵。

       假设我们采用Bellman-Ford算法,

    for (int i = 1; i < numOfVertex; i ++)      //这里循环从1开始是因为开始节点已经存放在S中了,还有numOfVertex-1个节点要处理       
    {      
    	for(int start=0;start<numOfVertex;start++)  
    	{  
    		for (int j =0; j < numOfVertex; j ++)    
    		{  
    			if (j!= startVertex  && map[start][j] < INT_MAX)  //在Q中,有距离的为c->d,c->e, c->b   
    			{   
    				int currentdist = distance[ start] + map[ start ][ j ];      
    				if (currentdist < distance[ j ])  //distance[j = ]为开始到j的距离    
    				{      
    					distance[ j ] = currentdist;      
    					prevVertex[ j ] = start;      
    				}      
    			}      
    		}   
    	}  
    }  

     看看矩阵的乘法:

    1.     for(i=0;i<this->m;i++)    
    2.         for(j=0;j<m2.n;j++)    
    3.         {    
    4.             for(k=0;k<this->n;k++)    
    5.              {    
    6.                 m3.data[i][j]+=this->data[i][k]*m2.data[k][j];    
    7.              }    
    8.     
    9.         } 
    那么如果要用Floyd求全源最短路径可以加上一个for循环,内部的可以定义为矩阵乘法的结构。 

    二、采用动态规划思想

        Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3)。

        Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B。所以,我们假设Dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立,如果成立,证明从A到X再到B的路径比A直接到B的路径短,我们便设置Dis(AB) = Dis(AX) + Dis(XB),这样一来,当我们遍历完所有节点X,Dis(AB)中记录的便是A到B的最短路径的距离。

      但是这里我们要注意循环的嵌套顺序,如果把检查所有节点X放在最内层,那么结果将是不正确的,为什么呢?因为这样便过早的把i到j的最短路径确定下来了,而当后面存在更短的路径时,已经不再会更新了。

    给出如下的代码:

    #include <iostream>     
    #include <iostream>     
    #include <vector>     
    #include <stack>     
    using namespace std;     
        
    int map[][6] = {                     //定义无向图,或者有向图    
        {0, 6, 3, INT_MAX, INT_MAX, INT_MAX},    
        {6, 0, 2, 5,INT_MAX, INT_MAX},    
        {3, 2, 0, 3,4, INT_MAX},    
        {INT_MAX,5, 3, 0, 2, 3},    
        {INT_MAX,INT_MAX, 4, 2, 0, 5},   
     {INT_MAX,INT_MAX,INT_MAX,3,5,0}  
    };    
        
    void Dijkstra(    
                  const int numOfVertex,    /*节点数目*/    
                  const int startVertex,    /*源节点*/    
                  int (map)[][6],          /*有向图邻接矩阵*/    
                  int *distance,            /*各个节点到达源节点的距离*/    
                  int *prevVertex           /*各个节点的前一个节点*/    
                  )    
    {    
        vector<bool> isInS;                 //是否已经在S集合中     
        isInS.reserve(0);    
        isInS.assign(numOfVertex, false);   //初始化,所有的节点都不在S集合中 , 分配numOfVertex个字节   
            
        //step1  
     /*初始化distance和prevVertex数组*/    
        for(int i =0; i < numOfVertex; ++i)    
        {    
            distance[ i ] = map[ startVertex ][ i ];  //源节点到各个节点的距离,其中INT_MAX代表不可达  
            if(map[ startVertex ][ i ] < INT_MAX)  //如果是可达的  
                prevVertex[ i ] = startVertex;    
            else    
                prevVertex[ i ] = -1;       //表示还不知道前一个节点是什么     
        }    
        prevVertex[ startVertex ] = -1;  //源节点无前一个节点  
            
        /*开始使用贪心思想循环处理不在S集合中的每一个节点*/    
        isInS[startVertex] = true;          //开始节点放入S集合中     
            
            
     int currentVertex = startVertex;  
            
        for (int i = 1; i < numOfVertex; i ++)      //这里循环从1开始是因为开始节点已经存放在S中了,还有numOfVertex-1个节点要处理     
        {    
            //step2    
            /*在Q中选择u到j的distance最小的一个节点, 如第一步A到C,最后目标到D*/     
            int minDistance = INT_MAX;    
            for(int j = 0; j < numOfVertex; ++j)  //  
            {    
                if((isInS[j] == false) && (distance[j] < minDistance))//寻找初始currentVertexA到Q中distance最小的节点 最后为新的currentVertexC    
                {    
                    currentVertex = j;    
                    minDistance = distance[j];    
                }    
            }    
            isInS[currentVertex] = true;//将这个节点currentVertex放入S集合中       
                
             //step3  
            /*对这个新的currentVertexC做松弛计算,更新distance*/   
            for (int j =0; j < numOfVertex; j ++)    
            {    
                if (isInS[j] == false && map[currentVertex][j] < INT_MAX)  //在Q中,有距离的为c->d,c->e, c->b  
                {    
                    int currentdist = distance[ currentVertex] + map[ currentVertex ][ j ];    
                    if (currentdist < distance[ j ])  //distance[j]为开始到j的距离  
                    {    
                        distance[ j ] = currentdist;    
                        prevVertex[ j ] = currentVertex;    
                    }    
                }    
      }   
        }         
    }    
    void Display(int (arr)[][6], int numOfVertex)    
    {    
        for(int i=0;i<numOfVertex;++i)    
        {    
            for(int j=0;j<numOfVertex;++j)    
                cout<<arr[i][j]<<'\t';    
            cout<<endl;    
        }    
    }  
      
    void Floyd(      
                  const int numOfVertex,    /*节点数目*/            
                  int (map)[][6],          /*有向图邻接矩阵,传递二维数组,使用强制类型转换,只需要带入二维数组的指针即可*/      
                  int (distance)[][6],            /*各个节点到达源节点的距离*/      
                  int (prevVertex)[][6]           /*各个节点的前一个节点*/      
                  )      
    {    
        for(int i=0;i<numOfVertex;i++)  
        {  
            for(int j=0; j<numOfVertex;j++)  
            {  
                distance[i][j] = map[i][j]; //startVertex = i  
                if(i!=j && map[i][j]<INT_MAX)  
                    prevVertex[i][j] = i;  
                else  
                    prevVertex[i][j] = -1;  
            }  
        }    
       
        //add a loop, k  
    	//const int a = 2*numOfVertex;
    	int a =0, k=0,c=0;
        for(; k<numOfVertex && c<1;a++)  
        {  
    		k=a%numOfVertex;
    	    c=a/numOfVertex;
            for (int i = 0; i < numOfVertex; i ++)      //这里循环从1开始是因为开始节点已经存放在S中了,还有numOfVertex-1个节点要处理        
            {          
                for (int j =0; j < numOfVertex; j ++)    
          
                {     
                    if (map[k][j] < INT_MAX && distance[i][k]<INT_MAX && i!=j)  //start is i, dest is j, k is the road pass through  
                    {     
                        int newdist = distance[ i][k] + map[k ][ j ];    //add start i  
                        if (newdist < distance[i][ j ])  //distance[j]为开始到j的距离     
                        {      
                            distance[i][ j ] = newdist;      
                            prevVertex[i][ j ] = k;   
                        }      
                    }   
                }     
            }    
        }  
    }    
       
    void printPath(int des, int * preVertex)    
    {     
        if(preVertex[des]!=-1)     
            printPath(preVertex[des],preVertex);    
        cout<<des<<' ';   
    }    
       
    void print(int (pre)[][6],  int numOfVertex, int (dist)[][6])  
    {  
        for(int i=0;i <numOfVertex; i++)  
        {  
            for(int j=0;j<numOfVertex;j++)  
            {  
            printPath(j,pre[i]);
    		cout<<"distance is "<<dist[i][j]<<endl;
            }  
        }  
    } 
    
    int main (int argc, const char * argv[])      
    {      
        int distance[6];      
        int preVertex[6];     
        int distanceFloyd[6][6];  
        int preVertexFloyd[6][6];  
              
        for (int i =0 ; i < 6; ++i )  //源目标为i的     
        {       
            Dijkstra(6, i, map, distance, preVertex);      
    		for(int j=0;j<6;++j)    
    		{       
    			cout<<distance[j]<<' ';       
    		}   
    		cout<<endl;
    		for(int j =0; j < 6; ++j)       
    		{       
    			int index = j; //加上for目标为j的      
    			stack<int > trace;      
    			while (preVertex[index] != -1) {      
    				trace.push(preVertex[index]);     
    				index = preVertex[index];      
    			}      
    			cout << "路径:";      
    			while (!trace.empty()) {      
    				cout<<trace.top()<<" -- ";      
    				trace.pop();      
    			}      
    			cout <<j; //j     
    			cout <<" 距离是:"<<distance[j]<<endl;  //j                       
            }       
        }    
        cout<<"floyd............."<<endl;  
        Floyd(6, map, distanceFloyd,preVertexFloyd);   
        Display(distanceFloyd,6);  
    	cout<<"path"<<endl;
        print(preVertexFloyd,6,distanceFloyd);  
    	system("pause");         
        return 0;      
    } 
    

    对比可以看出Dijkstra和Floyd的结果,在Floyd算法中,如果最外层的k循环只进行一圈,可能会造成中间某个点之间的路径由于中间路径没有完全更新而导致无法更新求到正确的结果。如C=1中本例的结果如下:


    即5到节点0之间的距离为无穷。很明显的知道0到5的距离是9,由于这是无向图,5到0的距离也是9,所以将K循环两圈,及c<1改为c<2让他可以来的及更新值,得到如下的结果:



    展开全文
  • 计算完全最短路径的Floyd算法】定义算法思想原理算法描述 定义 Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于...
  • 基于map-reduce的并行最短路径算法

    千次阅读 2012-01-29 17:40:16
    译自:Data-Intensive Text Processing with MapReduce, Chap.5.2 ...其中对于节点数较少的图,用邻接矩阵表示较为方便,计算时也能充分应用矩阵计算的一些优势。但是当节点数特别大,需要借助map-reduce计
  • Mapreduce 是谷歌提出的一个分布式计算框架, 利用该框架, 能够让用户方便地利用多机并行处理数据。 该框架有两个重要的函数: Map 和 Reduce, Map 函数对整个输入数据进行处理, 按照用户定义的处理方式, 从输入...
  • 单源最短路径单机版的经典MapReduce算法是Dijkstra算法算法每次沿着一个中间顶点遍历这个图,根据到源点的距离确定优先级。在算法运行过程中维护一个堆,每次取堆顶的顶点进行计算,这里没有并行化,因为每次取堆...
  • Bellman-Ford,Dijkstra和Delta Stepping是广泛使用的单一源最短路径算法(SSSP)算法。 Dijkstra的算法提供了工作高效的实现,而Bellman-Ford提供了易于并行实现的范围。 增量步进算法在两者之间进行了权衡。 本文...
  • 正如名字所言,最短路径算法就是为了找到一个图中,某一个点到其他点的最短路径或者是距离。 最短路径算法一般分为四种情况: a) 无权重的最短路径 b) 有权重的最短路径 c) 边的权重为负的图 d) 无环的图 ps:...
  • 并行算法学习之单源最短路径

    千次阅读 2016-04-10 10:10:23
    单源最短路径问题是指从一个指定顶点s到其他所有顶点i之间的距离,因为是单一顶点到其他顶点的距离,所以称为单源。  设图G,E>是一个有向加权网络,其中V和E分别为顶点集合和边集合,其边权邻接矩阵为W,边上权值w...
  • SParry是最短路径计算工具包,主要的最短路径算法包括Dijkstra , Bellman-Ford , Delta-Stepping和Edge-Based进行了封装。 提供了基于CUDA的并行加速版本以提高开发效率。 同时,当图形太大而无法直接将其放置到...
  • 方法采用云计算中Hadoop的MapReduce并行编程模型,提高编码效率,同时将细粒度并行遗传算法和禁忌搜索算法结合,提高了寻优算法计算速度和局部寻优能力,进而提高最短路径的求解效率。仿真结果表明,该方法在计算...
  • 要想计算该网络的平均最短路径长度,无论是传统的Floyd,Dijkstra算法,还是基于MPI的并行算法,在现有的计算机资源下都难以实现。提出了二级网络的概念,并基于此给出了一种针对中国教育网的新算法,使得在可以接受的时间...
  • 单源最短路径Dijkstra并行程序 单源最短路径Dijkstra串行程序
  • MapReduce 最优路径算法

    2019-11-27 10:29:17
    一、相关知识 最优路径算法是无向图中满足通路上所有顶点(除起点、终点外)各异,所有边也各异的通路。...是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主...
  • 《云计算应用开发实验》ubuntu 16.04真机 + hadoop2.6 + 本地伪分布  Hadoop kmeans和最短路径算法
  • 利用MPI求解全源最短路径并行算法实现;text-indent:-32.25pt;mso-list:l0 level1 lfo1;tab-stops:list 32.25pt">黑体">一、 <span style=
  • 其中对于节点数较少的图,用邻接矩阵表示较为方便,计算时也能充分应用矩阵计算的一些优势。但是当节点数特别大,需要借助map-reduce计算时,用邻接表是更为合适的选择。每一行数据,key为NodeId,值为与这个节点...
  • 试设计一个算法,求图中一个源点到其他各顶点的最短路径。 (1)用邻接表表示图; (2)按长度非递减次序打印输出最短路径的长度及相应路径。
  • 各位读者,晚上好。 这篇博客继续介绍无环加权有向图方面的内容。...文章目录一、环加权有向图的最短路径算法二、优先级限制下的并行任务调度问题的关键路径方法2.1 最长路径2.2 优先级限制下的并...
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...
  • MPI之弗洛伊德最短路径算法

    千次阅读 2017-06-05 19:05:09
    查找资料时发现百度上竟然没有基于MPI的全源最短路径的介绍。 一、直接上代码。#include #include #include <string.h> /* for debugging */ #include <mpi.h>const int INFINITY = 1000000;void Read_matrix(int...
  • 1 简介 路径规划技术是目前众多应用技术领域的研究热点,具有重要的科研价值和广阔的应用前景。路径规划技术的核心内容就是规划算法。目前求解路径规划问题的...而蚁群算法具有并行性、正反馈性、求解精度高、收敛速度

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,065
精华内容 4,026
关键字:

并行计算最短路径算法