Dijkstra（迪杰斯特拉）算法最短路径搜寻算法

发布时间：2016-09-12责任编辑：朱明浏览：1513

项目进展中遇到了需要寻找最短路线的方法，网上查了资料发现这个动图，瞬间明白要领，因为需求和他的不同，不看他的代码，自己实现一个。

动图如下：

项目中地图如下：

先介绍一下我的思路

1、每个路口标记上数字以便区分；

2、接下来是将地图交通图数据化，即整理成数组，数组命名int ways[][]；路口1中的1作为数组的下标，通往的方向为数组成员，即

ways[路口1] [路口2];

ways[路口2] [路口1，路口3，路口5]; ... ...

简化为ways[92][4] {{2,0,0,0},{1,3,5,0},... ...}，方向最多的有4个路口，空缺的由0补齐；

3、举例计算从2到21的步骤，

开始：创建一个数组分别存放已经计算过的点V1，本次步骤需要计算的点V2和下次需要计算的点V3；将路口2放到V2中，V2[]{2};

第一步：从V2中获取每一个路口的下一个路口并检测下一个路口是否已经计算过，若没有则保存在V3，同时保存到V1；V1[] {1,3,5}; V2[]{2}; V3[]{1,3,5}

第二步：将V2表清空，将V3表中数据存到V2中，重复第一步； V1[] {1,3,5,4,6,8,}; V2[]{1,3,5}; V3[]{4,6,8};

第三步：重复第二步，V1[] {1,3,5,4,6,8,7,20}; V2[]{4,6,8}; V3[]{7,20};

第四步：重复第二步，V1[] {1,3,5,4,6,8,7,209,21,22}; V2[]{7,20}; V3[]{9,21,22}; 判断路口中有等于21的结束循环，也就是路口2需要走4步到达21;

输出最短步骤 4；

4、计算路径

创建一个数组V4[92]，数组中都初始化为-1；在上面步骤中每当计算到改点，把当前步骤数记录在V4中；

寻找路径倒序寻找，

开始：创建vector数组path[]，将21放进去；

第一步：在V4[]中寻找值等于3的下标数{7,20}，path数组最后一个21的路口方向包含{20,23},将共同包含的20放到path[]中；

第二步：在V4[]中寻找值等于2的下标数{4,6,8}，path数组最后一个20的路口方向包含{8,21,22},将共同包含的8放到path[]中；

第三步：在V4[]中寻找值等于1的下标数{1,3,5}，path数组最后一个8的路口方向包含{5,20},将共同包含的5放到path[]中；

第四步：在V4[]中寻找值等于0的下标数{2}，path数组最后一个5的路口方向包含{2,6,8},将共同包含的2放到path[]中；

倒序输出path数组，2->5->8->20->21

代码如下：

//将每个路口可通往的方向记录在数组中，方向小于4个的用0补齐；

int ways[92][4] {

{2,0,0,0},{1,3,5,0},{2,4,0,0},{3,0,0,0},{2,6,8,0},{5,7,0,0},{6,9,0,0},{5,20,0,0},{7,10,0,0},{9,11,0,0},{10,12,0,0},{11,13,0,0},{12,14,0,0},

{13,15,0,0},{14,16,0,0},{17,15,36,0},{16,18,54,0},{17,19,0,0},{18,0,0,0},{8,21,22,0},{20,23,0,0},{20,37,0,0},{21,24,25,0},{23,26,0,0},

{23,26,0,0},{24,25,27,42},{26,28,43,0},{27,29,0,0},{28,30,33,0},{29,31,0,0},{30,32,0,0},{31,33,34,0},{29,32,46,0},{32,35,0,0},{34,36,0,0},

{16,35,0,0},{22,38,0,0},{37,39,0,0},{38,40,0,0},{39,41,55,0},{40,42,0,0},{26,41,43,60},{27,42,44,0},{43,45,80,0},{44,46,0,0},{33,45,47,0},

{46,48,0,0},{47,49,0,0},{48,50,81,0},{49,51,0,0},{50,52,84,0},{51,53,0,0},{52,54,0,0},{17,53,0,0},{40,56,0,0},{55,57,0,0},{56,58,61,0},

{57,79,0,0},{58,60,0,0},{59,42,0,0},{57,62,85,0},{61,63,0,0},{62,64,0,0},{63,65,66,0},{64,72,0,0},{64,67,0,0},{66,68,0,0},{67,69,0,0},

{68,70,80,0},{69,71,0,0},{70,75,0,0},{65,7,74,75},{72,74,0,0},{72,73,75,0},{71,72,74,76},{75,77,0,0},{76,78,0,0},{77,79,81,82},{78,80,0,0},

{44,69,79,0},{49,78,83,0},{78,83,0,0},{81,82,84,0},{83,51,0,0},{61,86,0,0},{85,87,88,0},{86,88,0,0},{86,87,89,0},{88,90,0,0},{89,91,0,0},{90,92,0,0},{91,0,0,0}

};

std::vector ishaveWay;//用于保存已经计算过的路口

std::vector nextWay;//用于记录下一步将要计算的路口，一循环一清除

std::vector currWay;//用于记录当前将要计算的路口，一循环开始获取nextWay的数据

int stepWay[92];//用于记录第几步到达该路口

for (int i0;i<92;i++)

{

stepWay[i] -1;

}

//计算从5到78吧

int beginWay 5;

int lastway 78;

//step 记录的第几步骤

nextWay.push_back(beginWay);

stepWay[beginWay-1] 0;

for (int step 1;;step++)

{

//将下一步计算的路口拿到当前

currWay.swap(nextWay);

//清空下一步将要计算的的路口

std::vector vv;

nextWay.swap(vv);

for (int item:currWay)

{

for (int i0;i<4;i++)//循环遍历当前路口指向的下一个路口

{

if(ways[item-1][i] ! 0)

{

if (ways[item-1][i] lastway)//如果到达目的地则输出后退出

{

log("beganway d, lastway d, step d",beginWay,lastway,step);

stepWay[item-1] step;

//打印路径

std::vector path;

path.push_back(lastway);

//反方向找回

for (step;step>0;step--)

{

for (int ii0;ii<92;ii++)

{

if (stepWay[ii-1] step)//找出该步骤的所有的路口

{

for (int jj0;jj<4;jj++)

{

if(ways[ii-1][jj] path.back())//找到能通往后一个路口的上一个路口

{

path.push_back(ii);

}

for (int k path.size()-1;k>0;k--)

{

log("pathItem d",path.at(k));

}

return true;

}

//判断是否包含在计算过的路口中

bool b_ishave false;

for (int haveitem : ishaveWay)

{

if (haveitem ways[item-1][i])

{

b_ishave true;

break;

}

if (!b_ishave)

{

nextWay.push_back(ways[item-1][i]);

ishaveWay.push_back(ways[item-1][i]);

stepWay[item-1] step;

}

输出结果：

beganway 5, lastway 78, step 12

pathItem 5

pathItem 8

pathItem 20

pathItem 21

pathItem 23

pathItem 24

pathItem 26

pathItem 27

pathItem 43

pathItem 44

pathItem 80

pathItem 79

pathItem 78

以下是所有代码：

HelloWorld.cpp文件

#include "HelloWorldScene.h"

USING_NS_CC;

Scene* HelloWorld::createScene()

{

// 'scene' is an autorelease object

auto scene Scene::create();

// 'layer' is an autorelease object

auto layer HelloWorld::create();

// add layer as a child to scene

scene->addChild(layer);

// return the scene

return scene;

}

// on "init" you need to initialize your instance

bool HelloWorld::init()

{

//////////////////////////////

// 1. super init first

if ( !Layer::init() )

{

return false;

}

Size visibleSize Director::getInstance()->getVisibleSize();

Vec2 origin Director::getInstance()->getVisibleOrigin();

/////////////////////////////

// 2. add a menu item with "X" image, which is clicked to quit the program

// you may modify it.

// add a "close" icon to exit the progress. it's an autorelease object

auto closeItem MenuItemImage::create(

"CloseNormal.png",

"CloseSelected.png",

CC_CALLBACK_1(HelloWorld::menuCloseCallback, this));

closeItem->setPosition(Vec2(origin.x + visibleSize.width - closeItem->getContentSize().width/2 ,

origin.y + closeItem->getContentSize().height/2));

// create menu, it's an autorelease object

auto menu Menu::create(closeItem, NULL);

menu->setPosition(Vec2::ZERO);

this->addChild(menu, 1);

/////////////////////////////

// 3. add your codes below...

// add a label shows "Hello World"

// create and initialize a label

auto label Label::createWithTTF("Hello World", "fonts/Marker Felt.ttf", 24);

// position the label on the center of the screen

label->setPosition(Vec2(origin.x + visibleSize.width/2,

origin.y + visibleSize.height - label->getContentSize().height));

// add the label as a child to this layer

this->addChild(label, 1);

// add "HelloWorld" splash screen"

auto sprite Sprite::create("HelloWorld.png");

// position the sprite on the center of the screen

sprite->setPosition(Vec2(visibleSize.width/2 + origin.x, visibleSize.height/2 + origin.y));

// add the sprite as a child to this layer

this->addChild(sprite, 0);

int ways[92][4] {

{2,0,0,0},{1,3,5,0},{2,4,0,0},{3,0,0,0},{2,6,8,0},{5,7,0,0},{6,9,0,0},{5,20,0,0},

{7,10,0,0},{9,11,0,0},{10,12,0,0},{11,13,0,0},{12,14,0,0},{13,15,0,0},{14,16,0,0},

{17,15,36,0},{16,18,54,0},{17,19,0,0},{18,0,0,0},{8,21,22,0},{20,23,0,0},{20,37,0,0},{21,24,25,0},{23,26,0,0},{23,26,0,0},

{24,25,27,42},{26,28,43,0},{27,29,0,0},{28,30,33,0},{29,31,0,0},{30,32,0,0},{31,33,34,0},{29,32,46,0},{32,35,0,0},{34,36,0,0},

{16,35,0,0},{22,38,0,0},{37,39,0,0},{38,40,0,0},{39,41,55,0},{40,42,0,0},{26,41,43,60},{27,42,44,0},{43,45,80,0},{44,46,0,0},

{33,45,47,0},{46,48,0,0},{47,49,0,0},{48,50,81,0},{49,51,0,0},{50,52,84,0},{51,53,0,0},{52,54,0,0},{17,53,0,0},{40,56,0,0},

{55,57,0,0},{56,58,61,0},{57,79,0,0},{58,60,0,0},{59,42,0,0},{57,62,85,0},{61,63,0,0},{62,64,0,0},{63,65,66,0},{64,72,0,0},

{64,67,0,0},{66,68,0,0},{67,69,0,0},{68,70,80,0},{69,71,0,0},{70,75,0,0},{65,7,74,75},{72,74,0,0},{72,73,75,0},{71,72,74,76},

{75,77,0,0},{76,78,0,0},{77,79,81,82},{78,80,0,0},{44,69,79,0},{49,78,83,0},{78,83,0,0},{81,82,84,0},{83,51,0,0},{61,86,0,0},

{85,87,88,0},{86,88,0,0},{86,87,89,0},{88,90,0,0},{89,91,0,0},{90,92,0,0},{91,0,0,0}

};

std::vector ishaveWay;//用于保存已经计算过的路口

std::vector nextWay;//用于记录下一步将要计算的路口，一循环一清除

std::vector currWay;//用于记录当前将要计算的路口，一循环开始获取nextWay的数据

int stepWay[92];//用于记录第几步到达该路口

for (int i0;i<92;i++)

{

stepWay[i] -1;

}

//计算从5到59吧

int beginWay 5;

int lastway 78;

//step 记录的第几步骤

nextWay.push_back(beginWay);

stepWay[beginWay-1] 0;

for (int step 1;;step++)

{

//将下一步计算的路口拿到当前

currWay.swap(nextWay);

//清空下一步将要计算的的路口

std::vector vv;

nextWay.swap(vv);

for (int item:currWay)

{

for (int i0;i<4;i++)//循环遍历当前路口指向的下一个路口

{

if(ways[item-1][i] ! 0)

{

if (ways[item-1][i] lastway)//如果到达目的地则输出后退出

{

log("beganway d, lastway d, step d",beginWay,lastway,step);

stepWay[item-1] step;

//打印路径

std::vector path;

春秋工作室供稿

Dijkstra（迪杰斯特拉）算法 最短路径搜寻算法

Dijkstra（迪杰斯特拉）算法最短路径搜寻算法