最短路径Dijkstra算法.docx

#include<iostream>
using namespace std;
#define MAXVEX 20
#define MAXARC 100
#define MAX 100
//辅助数组
int s[MAX];
#include<iostream>
using namespace std;
#define MAXVEX 20
#define MAXARC 100
#define MAX 100
//辅助数组
int s[MAX];
int path[MAX];
int d[MAX];
//邻接矩阵定义
struct ALGraph
{
char vexs[MAXVEX];//顶点向量
int arcs[MAXVEX][MAXVEX];//邻接矩阵
int vexnum;//顶点数
int arcnum;//边数
};
ALGraph G;//申明一个无向图的邻接矩阵类型
class Dijkstra
{
public:
int Locatevex(ALGraph G,char v);//图的基本操作，寻找顶点位置的下标
void CreateALGraph(ALGraph &G);//创建一个无向图的邻接矩阵表示
int Choose(ALGraph G,int d[],int s[]);//选出最小的d[i]
void dijkstra(ALGraph G,int v,int s[],int d[]);//Dijkstra算法
};
#include ""
//图的基本操作，寻找顶点位置的下标
int Dijkstra::Locatevex(ALGraph G,char v)
{
int i=0;
while(i< && v!=[i])
i++;
if(i<)
return i;
else
return -1;
}
//创建一个有向图的邻接矩阵表示
void Dijkstra::CreateALGraph(ALGraph &G)
{
char v1,v2;
int w;
cout<<"请输入图的顶点数和边数：";
cin>>>>;
cout<<"请输入顶点值："<<endl;
for(int i=0;i<;i++)//构造顶点向量
cin>>[i];
for(int p=0;p<;p++)//初始化邻接矩阵(开始时所有都为MAX，表示所有顶点都不相连)
for(int q=0;q<;q++)
[p][q]=MAX;
for(int k=0;k<;k++)//构造邻接矩阵
{
cout<<"输入边的顶点和权值："<<endl;
cin>>v1>>v2>>w;
int a=Locatevex(G,v1);
int b=Locatevex(G,v2);
[a][b]=w;
}
cout<<"有