丰北桥宾馆:dijkstra算法的改进程序

最近在搞毕业论文,搞的是Dijkstra算法的优化,改进的就是对最小权值的顶点搜索方法.首先使用快速排序函数对最短函数对最短路径值数组进行地址排序,并且使位置指针指向当前最小权值在地址数组的位置.接下来,使用邻接表实现松弛操作,即Dijkstra算法中修改未标记节点的权值的步骤:
if dist[j]=cost[J,k]<dist[k]
then dist[k]+dist[j]+cost[j,k]
再需要使用地址数组重新排序,再松弛.
我编的程序如下:
主要步骤：
1：开始：输入图的有关信息（以邻接表存储）；
2：利用图的广度优先搜索策略，判别顶点Vi到顶点Vj的路径是否存在，若存在，则进行步骤3和4，否则，退出计算；
3：使用快速排序函数对最短路径值数组进行地址排序，并且使位置指针指向当前最小权值在地址数组的位置；
4：使用邻接表实现松弛操作，即Dijkstra算法中修改未标记节点的权值的步骤：
IF dist[j]+cost[j,k]<dist[k]
Then dist[k]=dist[j]+cost[j,k]
5 :使用地址数组重新排序
6：一直找到源节点和末节点两个节点之间的最短路径；
7：输出源节点与其他节点的路径和权值。
8：算法结束

#include <stdio.h>
#define maxvertexnum 100
#define queues I
#define MAX n /* 定义最大顶点个数n为某一正整数*/

type struct EdgeNode /*建立有向图的邻接表 */
{ int adjnum; /*领接点域,存储位置序号为int型*/
DataType info;
struct EdgeNode *nextarc; /*链域,指向下一条边(弧)的指针*/
}EdgeNode;

typedef struct Vnode /*表头结点的类型VNode*/
{DataType vexdata; /*表头结点的数据域*/
structEdgeNode *firstarc; /*表头结点的指针域*/
}VNode;

typedef VNode AdGraph[MAX+1]; /*定义图的类型AdGraph为一个一维数组*/

void creatgraph(AdGraph G)/*建立领接表*/
{int i,n,e,*p=g,v1,v2; /*假设顶点数据为int型*/
scanf("%d,%d",&n,&e); /*输入图g的顶点数n和边数e*/
for(i=1;i<=n;i++)
{scanf("%d,",p[i].vexdata); /*输入各顶点值,设为int型*/
p[i].firstarc=NULL;
}
for(k=1;k<=e;k++) /*输入e条边*/
{scanf("%d,%d",&v1,&v2); /*输入图g的顶点数v1和v2*/
i=locateVex(G,v1);
j=locateVex(G,v2);/*确定两个顶点在图中的位置序号分别为i,j*/
if(i!=0&&j!=0) /*如果输入的顶点在图中*/
{r=(VNode*)malloc(sizeof(VNode));
r->adjnum=j;
r->Nextarc=p[i]->firstarc; /*链入链表中*/
p[i]->firstarc=r;
r=(VNode*)malloc(sizeof(Vnode)
r->adjnum=i;
r->nextarc=p[j]->firstarc /*链入链表中*/
p[j]->firstarc=r;
}
}
}
void quickSort(SortObject * pvector , int l,int r) /*快速排序算法*/
{
int i,j ;
RecordNode temp;
if(l>=r)return; /*只有一个记录或无记录，则无需排序*/
i=l;j=r;temp=pvector->record[i];
while(i!=j) /*寻找Rl的最终位置*/
{
while((pvector->record[j].key)&&(j>i))
j--; *从右向左扫描，查找第1个排序码小于temp.kep的记录*/
if(i<j)
pvector->record[i++]=pvector->record[j];
while((pvector->record[i].key<=temp.key)&&(j>i))
i++; /*从左向右扫描,查找第1个排序码大于temp.key的记录*/
if(i<j)
pvector->record[i]=temp; /*找到Rl的最终位置*/
quickSort(pvector,l,i-1); /*递归处理左区间*/
quickSort(pvector,i+1,r); /*递归处理右区间*/
}