7-2 迪杰斯特拉方法实现最短路径
用迪杰斯特拉算法实现有向网的最短路径
输入格式:
第一行输入有向网的顶点和边数，第二行输入各顶点值，用空格间隔，第三行开始输入各条边的 两个点的及边上的权值，用空格间隔。最后一行输入要求路径的两个顶点。
输出格式:
输出最短路径经过的各顶点，中间用-->连接。
输入样例:
在这里给出一组输入。例如：
6 8
0 1 2 3 4 5
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0 3
输出样例:
在这里给出相应的输出。例如：
0-->4-->3#include<iostream>
using namespace std;
//迪杰特斯拉：邻接矩阵：一维数组+二维数组+点边数
typedef int VexType;
#define MVNum 100
#define MaxInt 32767
int S[MVNum],Path[MVNum],D[MVNum];//迪杰特斯拉的三个数组
typedef struct{
VexType vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G,VexType v)
{
for(int i=0;i<G.vexnum;++i)
if(G.vexs[i]==v)return i;
return -1;
}
void CreatAMGraph(AMGraph &G,int &err)
{
cin>>G.vexnum>>G.arcnum;//输入点数边数
for(int i=0;i<G.vexnum;++i)cin>>G.vexs[i];
for(int i=0;i<G.vexnum;++i)
for(int j=0;j<G.vexnum;++j)
G.arcs[i][j]=MaxInt; //初始化二维数组
for(int k=0;k<G.arcnum;++k)
{
VexType v1,v2;
int w;
cin>>v1>>v2>>w;
int i=LocateVex(G,v1),j=LocateVex(G,v2);
if(i==-1||j==-1) err=1;
else G.arcs[i][j]=w;//有向网，只用一次
}
}
void ShortestPath_DIJ(AMGraph G,int vo)
{
for(int v=0;v<G.vexnum;++v)//这里出的问题
{
S[v]=0;
D[v]=G.arcs[vo][v];
if(D[v]<MaxInt)Path[v]=vo;
else Path[v]=-1;
}
S[vo]=1;D[vo]=0;
// for(int i=0;i<G.vexnum;++i){
// if(G.arcs[vo][i]!=MaxInt)//说明i与vo有边的关系
// {
// D[i]=G.arcs[vo][i];
// Path[i]=vo;
// }
// }
for(int k=0;k<G.vexnum-1;++k)//对剩下的n-1个顶点进行计算
{
int wmin=MaxInt,vmin;//找权值最小和其下标
for(int w=0;w<G.vexnum;++w){//找权值最小的，纳入S中
if(!S[w]&&D[w]<wmin){
vmin=w;wmin=D[w];
}
}
S[vmin]=1;
for(int i=0;i<G.vexnum;++i){
if(!S[i]&&(D[vmin]+G.arcs[vmin][i]<D[i]))
{
D[i]=D[vmin]+G.arcs[vmin][i];
Path[i]=vmin;
}
}
}
}
int main()
{
AMGraph G;
int err=0;
VexType vo,ve;
CreatAMGraph(G,err);//err的值为1的时候说明在创建邻接矩阵的时候出现了错误
cin>>vo>>ve;
int i=LocateVex(G,vo),j=LocateVex(G,ve);
if(i!=-1&&j!=-1){
ShortestPath_DIJ(G,i);
int adj[MVNum],k=1;
adj[0]=j;
while(Path[j]!=i)
{
adj[k]=Path[j];
j=Path[j];
++k;
}
adj[k]=i;
for(int n=k;n>=0;--n){
if(n!=0)cout<<G.vexs[adj[n]]<<"-->";
else cout<<G.vexs[adj[n]];
}
}
return 0;
}