otmdijkstra.cpp

Dijkstra算法

#include<stdio.h>//d为带正权的有向图，求从v0到d中其余各顶点间的最短路径。
#include<stdlib.h>
#define LEN sizeof(struct node)
#define NULL 0 
#define max 32767
struct node{int k,w;struct node *next;}*gr[101];
struct record{int v,d,p;}q[101];
int n,root,i,qpos[101],hs;
void swap(int a,int b)
{
	int i;
	struct record t;
	t.v=q[a].v;
	t.d=q[a].d;
	t.p=q[a].p;
	q[a].v=q[b].v;
	q[a].d=q[b].d;
	q[a].p=q[b].p;
	q[b].v=t.v;
	q[b].d=t.d;
	q[b].p=t.p;
	i=qpos[q[a].v];
	qpos[q[a].v]=qpos[q[b].v];
	qpos[q[b].v]=i;
}
void heapfy(int i)
{
	int m;
	m=i;
	do
	{
		i=m;
		if(2*i<=hs&&q[i*2].d<q[m].d)m=2*i;
		if(i*2+1<=hs&&q[i*2+1].d<q[m].d)m=2*i+1;
		if(i!=m)swap(i,m);
	}while(i!=m);
}
void decrease(int v,int k)
{
	q[v].d=k;
	while(v!=1&&q[v].d<q[v/2].d)
	{
		swap(v,v/2);
		v=v/2;
	}
}
void relax(int u,int v,int w)
{
	if(q[qpos[v]].d>q[qpos[u]].d+w)
	{
		q[qpos[v]].p=u;
		decrease(qpos[v],q[qpos[u]].d+w);
	}
}
void print(int s)
{
	if(s==root)
		printf("%d",root);
	else
	{
		print(q[qpos[s]].p);
		printf("->%d",s);
	}
}
void main()
{
	int i,u,v,m,w;
	struct node *p;
	scanf("%d%d",&n,&root);
	for(i=1;i<=n;i++)
        gr[i]=NULL;
    scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
        p=(struct node*)malloc(LEN);
		(*p).k=v;
		(*p).w=w;
		(*p).next=gr[u];
		gr[u]=p;
	}
	for(i=1;i<=n;i++)
	{
		q[i].v=i;
		q[i].d=max;
		qpos[i]=i;
	}
	q[root].d=0;
	swap(1,root);
	hs=n;
	while(hs!=0)
	{
		u=q[1].v;
		swap(1,hs);
		hs--;
		heapfy(1);
		p=gr[u];
		while(p!=NULL)
		{
			if(qpos[(*p).k]<=hs)
				relax(u,(*p).k,(*p).w);
			p=(*p).next;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(q[qpos[i]].d==max)
			printf("no way\n");
		else
		{
			print(i);
			printf(" %d\n",q[qpos[i]].d);
		}
	}
}