第C++實現(xiàn)Dijkstra算法的示例代碼EdgeNode*e=VexList[i].firstedge;

while(e){//然后就開始遍歷輸出每個邊表所存儲的鄰接點的下標

if(e-cost==-1){

cout"----"e-adjvex;

else{

cout"--"e-cost"--"e-adjvex;

e=e-next;

coutendl;

voidGraphList::CreateGraph(){

EdgeNode*e=newEdgeNode();

cout"請輸入頂點數(shù)和邊數(shù)："endl;

cinVertexsEdges;

cout"請輸入頂點的信息："endl;

for(inti=0;iVertexs;++i){

VertexListtmp;

cintmp.Vexs;

tmp.firstedge=NULL;

VexList.push_back(tmp);

for(intk=0;kEdges;++k){

inti,j;//(Vi，Vj)

doublecost;

cout"請輸入邊（Vi,Vj）與cost："endl;

cinijcost;

if(VexList[i].firstedge==NULL){//當前頂點i后面沒有頂點

e=newEdgeNode;

e-adjvex=j;

e-cost=cost;

e-next=NULL;

VexList[i].firstedge=e;

else{//當前i后面有頂點

EdgeNode*p=VexList[i].firstedge;

while(p-next){

p=p-next;

e=newEdgeNode;

e-adjvex=j;

e-cost=cost;

e-next=NULL;

p-next=e;

2.PathFinder類

PathFinder類用于搜索最短路徑

pathFinder.h

#ifndefPATH_FINDER_H

#definePATH_FINDER_H

#includeiostream

#includegraph.h

#includequeue

enumState{OPEN=0,CLOSED,UNFIND};

//定義dijkstra求解器

classDijNode{

public:

DijNode();

DijNode(double_val);

~DijNode(){};

doublegetCost(){returnm_cost;}

StategetState(){returnm_state;}

voidsetCost(double_val){m_cost=_val;}

voidsetState(State_state){m_state=_state;}

intgetIndex(){returnm_index;}

voidsetIndex(int_idx){m_index=_idx;}

voidsetPred(DijNode*_ptr){preNode=_ptr;}

DijNode*getPred(){returnpreNode;}

VertexListVertex;

private:

intm_index;

doublem_cost;//起點到當前點的代價

Statem_state;

DijNode*preNode;//保存父節(jié)點

typedefDijNode*DijNodePtr;

//構造優(yōu)先隊列用的

structcmp{

booloperator()(DijNodePtra,DijNodePtrb){

returna-getCost()b-getCost();

classPathFinder{

public:

priority_queueDijNodePtr,vectorDijNodePtr,cmpopenList;//用優(yōu)先隊列做openList，隊首元素為最小值

vectorDijNodePtrm_path;//存放最終路徑

PathFinder(){

openList.empty();

m_path.clear();

~PathFinder(){};

voidStoreGraph(GraphListPtr_graph);

voidSearch(intstart,intend);

voidretrievePath(DijNodePtr_ptr);

vectorDijNodePtrNodeList;

private:

GraphListPtrm_graph;

/*vectorDijNodePtrNodeList;*/

typedefPathFinder*PathFinderPtr;

#endif

PathFinder.cpp

#includePathFinder.h

DijNode::DijNode(){

m_cost=-1;//-1表示未被探索過，距離為無窮，非負數(shù)表示已經被探索過

m_index=-1;

m_state=UNFIND;//OPEN表示openlist，CLOSED表示在closeList中，UNFIND表示未探索過

preNode=nullptr;

DijNode::DijNode(double_val){

m_cost=_val;//-1表示未被探索過，非負數(shù)表示已經被探索過

m_index=-1;

m_state=UNFIND;//OPEN表示openlist，CLOSED表示在closeList中，UNFIND表示未探索過

preNode=nullptr;

voidPathFinder::StoreGraph(GraphListPtr_graph){

for(inti=0;i_graph-VexList.size();++i){

DijNodePtrnode=newDijNode();

node-Vertex=_graph-VexList[i];

node-setIndex(i);

NodeList.push_back(node);

voidPathFinder::Search(intstart,intend){

//搜索起點

DijNodePtrm_start=NodeList[s