迪杰斯特拉算法.cpp

迪杰斯科拉算法：从某个源点到其余各顶点的最短路径

/*关于图的最短路径问题
医院选址问题 
问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题． 
谁能提供思路或者C++代码更好，谢谢各位大虾了，打的好愿意追加更多得分
提问者： 说唱小生 - 助理 二级 最佳答案
医院选址 
1. 
代码如下*/

#include <iostream> 
using namespace std; 
#define MAXV 50 
#define INF 32767 
typedef int InfoType; 
//邻接矩阵存储方法 
typedef struct 
{ 
int no; 
InfoType info; 
} VertexType; 
typedef struct 
{ 
int edges[MAXV][MAXV]; 
int n,e; 
VertexType vexs[MAXV]; 
} MGraph; 
//狄克斯特拉算法 
void Ppath(int path[],int i,int v) 
{ 
int k; 
k=path[i]; 
if(k==v) return; 
Ppath(path,k,v); 
cout<<k; 
} 
int biaoji1=0,biaoji2=0; 
void Dispath(int dist[],int path[],int s[],int n,int v) 
{ 
int i; 
for(i=0;i<n;i++) 
{ 
if(i==v) continue; 
if(s[i]==1) 
{ 
cout<<"从"<<v<<"到"<<i<<"的最短路径为："<<dist[i]<<" "; 
cout<<v; 
Ppath(path,i,v); 
cout<<i<<endl; 
if(biaoji1!=5) 
{biaoji2+=dist[i];biaoji1++;} 
else 
{ 
cout<<"和为："<<" "<<biaoji2; 
biaoji1=0;biaoji2=0; 
} 
} 
else 
cout<<"从"<<v<<"到"<<i<<"不存在的路径"<<endl; 
} 
} 
void Dijkstra(MGraph g,int v) 
{ 
int dist[MAXV],path[MAXV]; 
int s[MAXV]; 
int mindis,i,j,u; 
for(i=0;i<g.n;i++) 
{ 
dist[i]=g.edges[v][i]; 
s[i]=0; 
if(g.edges[v][i]<INF) path[i]=v; 
else path[i]=-1; 
} 
s[v]=1;path[v]=0; 
for(i=0;i<g.n;i++) 
{ 
mindis=INF; 
for(j=0;j<g.n;j++) 
{ 
if(s[j]==0&&dist[j]<mindis) 
{ 
u=j; 
mindis=dist[j]; 
} 
} 
s[u]=1; 
for(j=0;j<g.n;j++) 
{ 
if(s[j]==0) 
{ 
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]) 
{ 
dist[j]=dist[u]+g.edges[u][j]; 
path[j]=u; 
} 
} 
} 
} 
Dispath(dist,path,s,g.n,v); 
} 
//弗洛伊德算法 
void Ppath1(int path[][MAXV],int i,int j) 
{ 
int k; 
k=path[i][j]; 
if(k==-1) return; 
Ppath1(path,i,k); 
cout<<k; 
Ppath1(path,k,j); 
} 
void Dispath1(int A[][MAXV],int path[][MAXV],int n) 
{ 
int i,j; 
for(i=0;i<n;i++) 
{ 
for(j=0;j<n;j++) 
{ 
if(i==j) continue; 
if(A[i][j]==INF) 
{ 
if(i!=j) 
cout<<"从"<<i<<"到"<<j<<"不存在路径"<<endl; 
} 
else 
{ 
cout<<"从"<<i<<"到"<<j<<"的最短路径长度为:"<<A[i][j]<<" "; 
cout<<i; 
Ppath1(path,i,j); 
cout<<j<<endl; 
} 
} 
} 
} 
void Floyd(MGraph g) 
{ 
int A[MAXV][MAXV],path[MAXV][MAXV]; 
int i,j,k; 
for(i=0;i<g.n;i++) 
{ 
for(j=0;j<g.n;j++) 
{ 
A[i][j]=g.edges[i][j]; 
path[i][j]=-1; 
} 
} 
for(k=0;k<g.n;k++) 
{ 
for(i=0;i<g.n;i++) 
{ 
for(j=0;j<g.n;j++) 
{ 
if(A[i][j]>A[i][k]+A[k][j]) 
{ 
A[i][j]=A[i][k]+A[k][j]; 
path[i][j]=k; 
} 
} 
} 
} 
Dispath1(A,path,g.n); 
} 

//主函数 
int main() 
{ 
int i,j,n; 
MGraph g; 
cout<<"请输入带权有向图的顶点个数：";//6 
while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/) 
{ 
cout<<"请输入带权有向图的邻接矩阵："<<endl; 
/* 
0 5 32767 7 32767 32767 
32767 0 4 32767 32767 32767 
8 32767 0 32767 32767 9 
32767 32767 5 0 32767 6 
32767 32767 32767 5 0 32767 
3 32767 32767 32767 1 0 
*/ 

for(i=0;i<n;i++) 
{ 
for(j=0;j<n;j++) 
{ 
//scanf("%d",&g.edges[i][j]); 
cin>>g.edges[i][j]; 
} 
} 
g.n=n; 
cout<<"采用狄克斯特拉算法得到的最短路径为："<<endl; 
for(i=0;i<n;i++) Dijkstra(g,i); 
cout<<endl; 
cout<<"采用弗洛伊德算法得到的最短路径为："<<endl; 
Floyd(g); 
cout<<endl; 
cout<<"请输入带权无向图的顶点个数："; 
} 
return 0; 
} 


//2.代码如下 

/*#include <iostream> 
using namespace std; 
int INFTY=32767; 
template<class T> 
class Graph 
{ 
public: 
virtual void Insert(int u,int v,T& w)=0; 
virtual void Remove(int u,int v)=0; 
virtual bool Exist(int u,int v)=0; 
virtual int Vertices()const {return n;} 
protected: 
int n,e; 

}; 
template <class T> 
class MGraph:public Graph<T>//邻接矩阵存储图 
{ 
public: 
MGraph(); 
~MGraph(); 
void Build_Graph(); 
void Insert(int u,int v,T& w); 
void Remove(int u,int v); 
bool Exist(int u,int v); 
void Floyd(T**&d,int**&path); 
int num; 
protected: 
T**a; 
T noEdge; 
}; 
template <class T> 
void MGraph<T>::Build_Graph()//建图 
{ 
cout<<"请输入顶点的个数："<<endl; 
int C_num; 
cin>>C_num; 
num=n=C_num;e=0;noEdge=INFTY; 
a=new T*[n]; 
for(int k=0;k<n;k++){ 
a[k]=new T [n]; 
for(int j=0;j<n;j++)a[k][j]=noEdge; 
a[k][k]=0; 
} 
cout<<"建立村庄编号为1--"<<C_num<<"的图"<<endl; 
for(int i=0;i!=C_num;i++) 
for(int j=i+1;j!=C_num;j++) 
{ 
int w; 
cout<<"请输入村庄"<<i+1<<"与村庄"<<j+1<<"之间的权值："; 
cin>>w; 
Insert(i,j,w); //向图中添加权值为W的边 
cout<<i<<"--->"<<j<<":"<<a[i][j]<<endl; 
} 
cout<<"*********************************************************************"<<endl; 
cout<<"已建立村庄编号为1--"<<C_num<<"的图:"<<endl; 
cout<<"**********************************"<<endl; 
cout<<" \t\t"; 
for(int b=1;b<=C_num;b++){ 

cout<<b<<"\t"; 
} 
cout<<endl; 
} 

template <class T> 
MGraph<T>::MGraph() 
{ 
Build_Graph(); 
} 

template <class T> 
MGraph<T>::~MGraph() 
{ 
for(int i=0;i<n;i++)delete[]a[i]; 
delete[]a; 
} 

template <class T> 
bool MGraph<T>::Exist(int u,int v) 
{ 
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false; 
return true; 
} 
template <class T> 
void MGraph<T>::Insert(int u,int v,T &w) 
{ 
a[u][v]=w;a[v][u]=w;e++; 
} 
template <class T> 
void MGraph<T>::Remove(int u,int v) 
{ 
a[u][v]=noEdge;e--; 
} 

template <class T> 
void MGraph<T>::Floyd(T**&d,int**&path)//所有顶点之间的最短路径 
{ 
int i,j,k; 
d=new T*[n];path=new int*[n]; 
for(i=0;i<n;i++){ 
d[i]=new T[n];path[i]=new int[n]; 
for(j=0;j<n;j++){ 
d[i][j]=a[i][j]; 
if(i!=j&& a[i][j]<INFTY)path[i][j]=i; 
else path[i][j]=-1; 
} 
} 
for(k=0;k<n;k++) 
for(i=0;i<n;i++) 
for(j=0;j<n;j++) 
if(d[i][k]+d[k][j]<a[i][j]){ 
d[i][j]=d[i][k]+d[k][j]; 
path[i][j]=path[k][j]; 
} 
} 
int main() 
{ 
MGraph<int> Hospital; 
int **d,**path; 
int i,j,n; 
n=Hospital.num; 
Hospital.Floyd(d,path); 
int *sum=new int[n]; 
cout<<endl; 
for(i=0;i!=n;i++)//输出矩阵 
{ 
cout<<i+1<<"\t\t"; 
sum[i]=0; 
for(j=0;j!=n;j++) 
{ 
sum[i]+=d[i][j]; 
cout<<d[i][j]<<"\t"; 
} 
cout<<endl; 
} 
cout<<"*********************************************************************"<<endl; 
int min=0; 
for(i=0;i!=n;i++) 
{ 
cout<<i+1<<"村庄："<<sum[i]<<endl; 
if(sum[min]>sum[i])//判断最短路径 
min=i; 
} 
cout<<"医院应在编号为"<<min+1<<"的村庄"<<endl; 
for(i=0;i<n;i++) 
{ 
delete[]d[i]; 
delete[]path[i]; 
} 
delete[]d; 
delete[]path; 
return 0; 
} */