Dijkstra算法的Matlab/C++代码

Dijkstra算法,中文名迪杰斯特拉算法,是图论中最常用的算法之一,用来解决图中一个点到其他所有点的最短路问题。Dijkstra算法的Matlab代码和C++代码其实网上很多,但是我还是给出我自己写的,感觉比网上那些用起来方便多了。C++的是通信网理论基础课上的作业,绝对不会有问题。Matlab的已经经历我多次做题的考验了,从未出现过问题……

还不知道Dijkstra算法?自行Google或者找本图论来看看吧。废话不多说,下面给出Dijkstra算法的Matlab和C++代码:

先是Matlab代码:

[code lang=”matlab”]

function[S,D]=minRoute(i,m,W,opt)
%由于使用次数太多了,没有注释,对几个参数解释一下
%S存放最短路的路径
%D存放最短路的距离
%i为起点节点
%m为节点数
%W为距离矩阵
%opt一般填1,将S矩阵排序输出,具体自己看代码就懂了
if nargin<4
opt=0;
end
dd=[];tt=[];
ss=[];ss(1,1)=i;
V=1:m;V(i)=[];
dd=[0;i];
kk=2;
[mdd,ndd]=size(dd);
while ~isempty(V)
[tmpd,j]=min(W(i,V));
tmpj=V(j);
for k=2:ndd
[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));
tmp2=V(jj);
tt(k-1,:)=[tmp1,tmp2,jj];
end
tmp=[tmpd,tmpj,j;tt];
[tmp3,tmp4]=min(tmp(:,1));
if tmp3==tmpd
ss(1:2,kk)=[i;tmp(tmp4,2)];
else
tmp5=find(ss(:,tmp4)~=0);
tmp6=length(tmp5);
if dd(2,tmp4)==ss(tmp6,tmp4)
ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];
else
ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];
end
end
dd=[dd,[tmp3;tmp(tmp4,2)]];
V(tmp(tmp4,3))=[];
[mdd,ndd]=size(dd);
kk=kk+1;
end
if opt==1
[tmp,t]=sort(dd(2,:));
S=ss(:,t);
D=dd(1,t);
else
S=ss;
D=dd(1,:);
end

[/code]

然后是C++代码,基于STL写的,功能都在头文件里实现了,用的时候直接包括这个头文件然后调用函数就行。有些功能也可以自己添加。

[code lang=”cpp”]

#ifndef CGRAPH_H
#define CGRAPH_H
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include "stdafx.h"
#include "CGraph.h"
#include <fstream>
using namespace std;

const int INFINITY=10000;
const int NUL = -1;
class CEdge{
private:
int head, tail;
int weight, capacity;
public:
CEdge(int a, int b, int c, int d);
CEdge(int a, int b, int w);
CEdge(CEdge & x);
~CEdge();
int getHead();
int getTail();
int getWeight();
int getCap();
bool operator<(CEdge& x);
};

class CVertex{
public:
int d;
int p;
int ID;
CVertex(int dis, int pre, int vid){d = dis; p = pre; ID = vid;}
~CVertex();
};

bool pVertexComp ( CVertex* x, CVertex* y );

class CGraph{
private:
int numVertex, numEdge;
list<CEdge*> IncidentList;
// 所有的顶点
map<int, CVertex*> mapVID_Vertex;
// 暂时标记的顶点集合
list<CVertex*> listTempMark;
// 记录与顶点关联的出度边
map<int, list<CEdge*> > mapVID_listEdge;
void Update(int VID);
public:
CGraph(char* inputFile);
CGraph(list<CEdge*> listEdge);
CGraph(CGraph &);
~CGraph();
int getNumVertex();
int getNumEdge();
list<CEdge*> getlist();
void DijkstraAlg(int VID);
void PrintShortestPath(int s, int d);
void PrintAllShortestPath(int s);
void DeleteIncidentList(int c);
};

int CEdge::getHead()
{
return head;
}
int CEdge::getTail()
{
return tail;
}
int CEdge::getWeight()
{
return weight;
}
int CEdge::getCap()
{
return capacity;
}
CEdge::CEdge(int a, int b, int w, int c)
{
head = a;
tail = b;
weight = w;
capacity = c;
}

bool pVertexComp ( CVertex* x, CVertex* y )
{ if ( x->d < y->d ) return true;
return false;
}

CGraph::CGraph(char* inputFile)
{
ifstream file(inputFile);
int numVertex = 0;
int numEdge = 0;
file>>numVertex>>numEdge;
for (int i = 0; i < numVertex; i++)
{
CVertex* vp;
vp = new CVertex(INFINITY, NUL, i);
mapVID_Vertex[i] = vp;
}
for (int i = 0; i< numEdge; i++)
{
int head, tail, weight,capacity; //对input函数进行修改,增加容量
file>>tail>>head>>weight>>capacity;
CEdge* ep = new CEdge(head, tail, weight,capacity);
IncidentList.push_back(ep);
list<CEdge*> templist;
templist = mapVID_listEdge[tail];
mapVID_listEdge[tail].push_back(ep);
}

file.close();
}

list<CEdge*> CGraph::getlist()
{
return IncidentList;
}

void CGraph::Update(int v)
{
list<CEdge*> lEdge = mapVID_listEdge[v];
list<CEdge*>::iterator i,iend;
iend = lEdge.end();
for( i = lEdge.begin(); i!=iend; i++)
{
int w = (*i)->getWeight();
CVertex* h = mapVID_Vertex[(*i)->getHead()];
CVertex* t = mapVID_Vertex[v];
if ( t->d + w < h->d )
{ h->d = t->d + w;
h->p = v;
}
}
}

void CGraph::DijkstraAlg(int s)
{
map<int, CVertex*>::iterator i,iend;
iend = mapVID_Vertex.end();
for( i=mapVID_Vertex.begin(); i != iend; i++)
{ if ( i->second->ID == s)
{
cout<< i->second->ID<<endl;
i->second->d = 0;
}
listTempMark.push_back(i->second);
}
Update(s);
while( ! listTempMark.empty() )
{ listTempMark.sort(pVertexComp);
int j = (*listTempMark.begin())->ID;
listTempMark.pop_front();
Update(j);
}
}

void CGraph::PrintShortestPath(int s, int d)
{
cout<< " the length of the shortest path from "<<s<<" to "<<d<<" is: "<<mapVID_Vertex[d]->d<<endl;
cout<< " the shortest path from "<<s<<" to "<<d<<" is: ";

list<int> shortest;
shortest.push_front(d);
int pre = d;
while(s!=pre)
{
pre = mapVID_Vertex[pre]->p;
shortest.push_front(pre);
}

list<int>::iterator beg, tempiter;
for(beg = shortest.begin();beg != shortest.end();beg++)
{
cout<<*beg << " ";

}
cout<<endl;
}

void CGraph::PrintAllShortestPath(int s)
{
map<int, CVertex*>::iterator mapiter ;
for (mapiter = mapVID_Vertex.begin(); mapiter != mapVID_Vertex.end(); mapiter++)
{
if ( s != mapiter->second->ID)
{
PrintShortestPath(s, mapiter->second->ID);
}
}
}

CGraph::~CGraph()
{
}

# endif

[/code]

其实还有基于Dijkstra改进的Dial算法,不过写的比较挫,先不放出来了。大家需要的自行复制过去研究,有不对的地方希望能指出,不甚感激。

发表评论

电子邮件地址不会被公开。 必填项已用*标注