关于迪杰斯特拉算法的问题，求改！！！！
#include<iostream.h>#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//#include <vector>
#define MAX_VERTEX_NUM 20
#define INFINITY 10000
#define maxWeight 10000
typedef int PathMatrix[MAX_VERTEX_NUM];
typedef int ShortestPathTable[MAX_VERTEX_NUM];
typedef char Vertex_Type[5];
typedef enum
{
DG,UDG
}Graph_Kind;
typedef struct Arc_Node
{
int adjvex; //邻接点在向量表中的位置
struct Arc_Node *nextarc;
int weight; //权
int *info;
}Arc_Node;
typedef struct Vertex_Node
{
Vertex_Type data;
Arc_Node *firstarc;
}Vertex_Node;
typedef struct
{
Vertex_Node vexs[MAX_VERTEX_NUM];//顶点向量
int vexnum; //顶点数
int arcnum;
Graph_Kind kind;
}ALGraph;
//初始化图中的有关信息
void Init_ALGraph(ALGraph &G)
{
int w;
//printf("输入图的类型(DG:1 UDG:2):");
cout<<"输入图的类型(DG:1 UDG:2):";
cin>>w;
//scanf("%S",&G.kind);
cout<<"输入图的顶点数:";
cin>>G.vexnum;
cout<<"输入图的边数:";
cin>>G.arcnum;
int i;
cout<<"输入定点值:";
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i].data;
G.vexs[i].firstarc=NULL;
}
}
//获取定点在向量中的位置 如果出错就终止运行
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(v,G.vexs[i].data)==0)
return i;
exit(0);
}
/*int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
for(int i=0;i<G.vexnum;++i)
{
if(G.vexs[i].data==v)
return i;
else
return 0;
}
}*/
void Greate_ALGraph(ALGraph &G)
{
Init_ALGraph(G);
Vertex_Type v1,v2;
int i,m,n;
cout<<"输入图形的边:";
for(i=0;i<G.arcnum;++i) //输入并构造邻接表
{
cin>>v1>>v2;
m=Get_Vertex_Location(G,v1); //确定i和j在G中位置，即顶点的序号
n=Get_Vertex_Location(G,v2);
Arc_Node *p1,*p2;
p1=(Arc_Node*)malloc(sizeof(Arc_Node));
p1->adjvex=n; //对弧结点赋邻接点位置信息
p1->nextarc=G.vexs[i].firstarc;
G.vexs[i].firstarc=p1;
switch(G.kind)
{
case DG:
break;
case UDG:
p2=(Arc_Node*)malloc(sizeof(Arc_Node));
p2->adjvex=m;
p2->nextarc=G.vexs[n].firstarc;
G.vexs[n].firstarc=p2; //头插入
break;
}
}
}
void ShortestPath_DIJ(ALGraph &G,int v0,PathMatrix &P,ShortestPathTable &D)
{
int v,w,i,min;
int final[MAX_VERTEX_NUM];
Arc_Node *p;
for(v=0;v<G.vexnum;v++) {
final[v]=false;
D[v]=INFINITY;
}
for(p=G.vexs[v0].firstarc;p;p=p->nextarc) {
D[p->adjvex]=*(int *)(p->info);
if(P[i]<maxWeight&&P[i]!=0)
{ P[p->adjvex]=v0;
P[p->adjvex]=p->adjvex;
}
else
P[i]=-1;
}
D[v0]=0;
final[v0]=true;
for(i=1;i<G.vexnum;i++) {
min=INFINITY;
for(w=0;w<G.vexnum;w++)
if(!final[w]&&D[w]<min) {
v=w;
min=D[w];
}
final[v]=true;
for(p=G.vexs[v].firstarc;p;p=p->nextarc) {
w=p->adjvex;
if(!final[w] && min<INFINITY && min+*(int *)(p->info)<D[w]) {
D[w]=min+*(int *)(p->info);
P[w]=P[v];
P[p->adjvex]=w;
}
}
}
}
void Print_ALGraph(ALGraph G)
{
int i;
for(i=0;i<G.vexnum;++i)
{
Arc_Node *p=G.vexs[i].firstarc;
while(p)
{
switch(G.kind)
{
case UDG:
cout<<G.vexs[i].data<<"--";
cout<<G.vexs[p->adjvex].data;
break;
case DG:
cout<<G.vexs[i].data<<"--";
cout<<G.vexs[p->adjvex].data<<endl;
break;
}
p=p->nextarc;
}
}
}
int main()
{
ALGraph G;
int v;
int n;
PathMatrix *P=new PathMatrix[n] ;
ShortestPathTable *D=new ShortestPathTable[n];
Greate_ALGraph( G );
ShortestPath_DIJ(G,v,P,D);
Print_ALGraph( G );
return 0;
}
[ 本帖最后由 世界模型 于 2010-12-7 22:11 编辑 ]
