dijkstra.cpp

经典的dijkstra求最短路径算法

#include<iostream.h>
#define MAX 65535
struct VNode{
	int vd;
	int w;
	VNode *next;
};
struct GNode{
	int vs;
	VNode *first;
};
struct Graph{
	GNode* h;
	int v_num,e_num;
	int kind;             //0表示无向图，1表示有向图
};
int** DIJ(Graph G,int v)
{
	int min,k;
	int *D=new int[G.v_num],*count=new int[G.v_num];
	int **sh=new int*[G.v_num];
	for(int i=0;i<G.v_num;i++) { sh[i]=NULL;D[i]=MAX; count[i]=0; }
	GNode* p=NULL;
	VNode* t=NULL;
	if(v>G.v_num-1) {cout<<"源点不存在！\n";return NULL;}
	p=G.h+v;
	t=p->first;
	while(t)
	{
		D[t->vd]=t->w;
		sh[t->vd]=new int[G.v_num];
		sh[t->vd][0]=v;
		count[t->vd]++;
		t=t->next;
	}
    for(i=1;i<G.v_num;i++)
	{
	    for(int j=0;j<G.v_num;j++)
		{
			min=MAX;
            if(min>D[j])
			{
			   min=D[j];
			   k=j;
			}  
		}
		//sh[k]=new int[G.v_num];
		sh[k][count[k]]=k;
		count[k]++;
		t=(G.h+k)->first;
		while(t)
		{
			if(D[t->vd]>D[k]+t->w)
			{
				D[t->vd]=D[k]+t->w;
				if(sh[t->vd])
				{
					for(j=0;j<count[k];j++) sh[t->vd][j]=sh[k][j];
			        count[t->vd]=count[k];
				}
				else
				{
					sh[t->vd]=new int[G.v_num];
					for(j=0;j<count[k];j++) sh[t->vd][j]=sh[k][j];
			        count[t->vd]=count[k];
				}
			}
			t=t->next;
		}
		D[k]=MAX;
    }
	return sh;
}

void main()
{
	Graph G={NULL,5,6,1};
	G.h=new GNode[5];
	for(int i=0;i<5;i++)
	{
		G.h[i].vs=i;
	    G.h[i].first=NULL;
	}
	VNode* p=new VNode;
	p->vd=1;
	p->w=1;
	p->next=NULL;
	G.h[0].first=p;
	p=new VNode;
	p->vd=2;
	p->w=3;
	p->next=NULL;
	G.h[0].first->next=p;
	p=new VNode;
	p->vd=1;
	p->w=1;
	p->next=NULL;
	G.h[2].first=p;
	p=new VNode;
	p->vd=3;
	p->w=1;
	p->next=NULL;
    G.h[2].first->next=p;
    p=new VNode;
	p->vd=4;
	p->w=1;
	p->next=NULL;
	G.h[2].first->next->next=p;
	p=new VNode;
	p->vd=3;
	p->w=2;
	p->next=NULL;
    G.h[1].first=p;
	int **q;
	q=DIJ(G,0);
	for(i=1;i<5;i++)
	{
		for(int j=0;q[i][j]!=i;j++)
			cout<<q[i][j]<<' ';
		cout<<i<<endl;
	}

}