7_42.cpp

以邻接表为存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法

#include <stdio.h> 
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define VertexType char //数据元素类型
int Vn=6,En=8; //实际顶点数，边或弧数
#define INFINITY 10000 
#define TRUE 1 
#define FALSE 0 
#define vexnum 6 
char Ve[vexnum+1]="ABCDEF";


// 邻接表存储结构
typedef struct ArcNode
{
	int adjvex; //邻接点在顺序表中的位置
	int info;
	struct ArcNode *nextarc; //指向下一个邻接点
}ArcNode,*AdjLink;

// 表头指针结构
typedef struct VNode
{
	VertexType data;
	//AdjLink HAdjV; //邻接点链表头指针
	ArcNode *firstarc;
} VNode;

// 图的邻接表存储结构
VNode AdjList[vexnum];
// 图的初始化
void GraphAdjLInit(VertexType *vs)
{
	if (Vn>vexnum) Vn=vexnum;
	for (int k=0; k<vexnum; ++k)
	{
		if (k<Vn) AdjList[k].data=vs[k];
		else AdjList[k].data=NULL;
		AdjList[k].firstarc=NULL;
	}
} //GraphAdjLInit

// 求顶点v在图G中的位置(下标)
int LocationV(VertexType v)
{
	for (int k=0; k<Vn; ++k)
		if (AdjList[k].data==v) return k;
	if (k>=vexnum) return -1;
	AdjList[k].data=v;
	Vn=k+1;
	AdjList[Vn].data=NULL;
	return k;
} //LocationV

// 通过输入“边”建立图的邻接表存储结构
void GraphAdjCreate(char v,char w,int weight)
{
	int j1=0,j2=0;
	AdjLink p,q;
        j1=LocationV(v);
       j2=LocationV(w); 
	 if (j1==-1) return;
	if (j2==-1) return;
		p=(AdjLink) malloc(sizeof(VNode));
		p->adjvex=j2;
		p->info=weight;
		p->nextarc=NULL;
		if (!AdjList[j1].firstarc) {AdjList[j1].firstarc=p;}
		else
		{
			q=AdjList[j1].firstarc;
			while (q->nextarc) q=q->nextarc;
			q->nextarc=p;
		}
	
} //GraphAdjCreate

// 显示图的邻接表存储结构
void GraphAdjLPrint()
{
	for(int k=0; k<Vn; ++k)
	{
		printf("%d [%c",k,AdjList[k].data);
		AdjLink p=AdjList[k].firstarc;
		if(p)printf(",*]->[");	
		while(p)
		{ if(p->nextarc)
		  printf("%d,%d,%d,*]->[",k,p->adjvex,p->info);
		else printf("%d,%d,%d",k,p->adjvex,p->info);
			p=p->nextarc;
		}
		printf(",^]\n");
	}
}//GraphAdjLPrint
int edgelen(int v,int w)
{AdjLink p=AdjList[v].firstarc;
while(p->adjvex!=w)p=p->nextarc;
return p->info;
}

void ALGraph_DIJ(int v0,int P[][vexnum],int D[])
//在邻接表存储结构上实现迪杰斯特拉算法
{
  int v; 
  int w; 
  int min; 
  int i,j;
  int final[vexnum];  
  for(v=0;v<vexnum;v++)
    D[v]=INFINITY;
  for(AdjLink p=AdjList[v0].firstarc;p;p=p->nextarc)
    D[p->adjvex]=p->info; //给D数组赋初值
  for(v=0;v<vexnum;v++)
  {
    final[v]=FALSE;
    for(w=0;w<vexnum;w++) P[v][w]=-1; //设空路径
    if(D[v]<INFINITY)
    {
      P[v][v0]=v;
      //P[v][v]=1;
    }
  }//for
  D[v0]=0;final[v0]=TRUE; //初始化
  for(i=1;i<vexnum;i++)
  {
    min=INFINITY;
    for(w=0;w<vexnum;w++)
      if(!final[w])
        if(D[w]<min) //尚未求出到该顶点的最短路径
        {
          v=w;
          min=D[w];
        }
    final[v]=TRUE;
    for(p=AdjList[v].firstarc;p;p=p->nextarc)
    {
      w=p->adjvex;
      if(!final[w]&&(min+(p->info)<D[w])) //符合迪杰斯特拉条件
      {
        D[w]=min+edgelen(v,w);
       for(j=0;j<vexnum;j++)
		P[w][j]=P[v][j];
        P[w][v]=w; //构造最短路径
      }
    }//for
  }//for
}//ALGraph_DIJ*/


void main()
{ 
printf("以邻接表为存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法\n");
GraphAdjLInit(Ve);
GraphAdjLPrint(); 
/***********弧的信息***************/
GraphAdjCreate(Ve[0],Ve[2],10);
GraphAdjCreate(Ve[0],Ve[4],30);
GraphAdjCreate(Ve[0],Ve[5],100);
GraphAdjCreate(Ve[1],Ve[2],5);
GraphAdjCreate(Ve[2],Ve[3],50);
GraphAdjCreate(Ve[3],Ve[5],10);
GraphAdjCreate(Ve[4],Ve[3],20);
GraphAdjCreate(Ve[4],Ve[5],60);

printf("\n初始有向图为:(v,w,weight) \n");
GraphAdjLPrint();

int P[vexnum][vexnum];
int D[vexnum];
int i,j,v0=0;
ALGraph_DIJ(0,P,D);
    //输出最短路径 
    for ( i = 0; i <vexnum; i++) 
    { 
        printf("Path %c to %c:\n",Ve[v0],Ve[i]); 
        if ( P[i][v0] != -1 )   //存在路径则输出 
        { 
            for (j = v0; j != -1; j = P[i][j]) 
            { 
                if (j != v0) 
                    printf("→"); 
                printf("%c",Ve[j]); 
            } 
            printf("\n"); 
        } 
        printf("Length:%d\n",D[i]); 
        printf("\n"); 
    } 
}