C dijkstra算法 最短路径 迪杰斯特拉.docx

#include <> //最短路径的输出部分参照的是曲文的
#include <>
#include ""
#define Max_num 40
#define Longest 100000
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
ifstream Input("");
typedef int Status;
typedef struct{
int num;
char name[50];
char info[100];
}VertexType;
typedef struct{
VertexType vexs[Max_num]; //顶点向量
int arcs[Max_num][Max_num];
int vexnum,um; //邻接矩阵
}AMGraph;
Status CreateGraph(AMGraph *G,int n, int m){ //构造图,n为顶点数目,m为边数
int i,j,k,f,w,a,b;
VertexType v1,v2;
for(i=1;i<=n;i++){ //输入顶点信息
G->vexs[i].num=i;
Input>>G->vexs[i].name>>G->vexs[i].info;
}
for(i=1;i<=n;i++) //初始化邻接矩阵
for(j=1;j<=n;j++)
G->arcs[i][j]=Longest;
for(k=0;k<m;k++){ //从文件读入边的信息
Input>>>>>>w;
for(f=1;f<=n;f++)
if(strcmp(,G->vexs[f].name)==0)
a=G->vexs[f].num;
for(f=1;f<=n;f++)
if(strcmp(,G->vexs[f].name)==0)
b=G->vexs[f].num;
G->arcs[a][b]=w;
G->arcs[b][a]=G->arcs[a][b];
}
return OK;
}
void viewschool(AMGraph *G)
{
int m;
cout<<"请输入要查询的景点代号:";
cin>>m;
cout<<endl;
cout<<G->vexs[m].name<<G->vexs[m].info<<endl;
}
void Dijkstra(AMGraph *G,int v1 ,int v2,int n)//用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Path[v]及其距离Dist[v]
//S[v]为真当且仅当v属于S,即已求得从vl到v的最短路径
{
int Path[Max_num];
int S[Max_num];
int D[Longest];
int w,v;
//n=G->vexnum;
for(v=1;v<=n;v++)
{
S[v