现在的位置: 首页 > 综合 > 正文

迪杰斯特拉(Dijkstra)算法—-C语言算法(线性表实现)

2013年10月07日 ⁄ 综合 ⁄ 共 8275字 ⁄ 字号 小 中 大 ⁄ 评论关闭

以下是程序部分：

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
#define Max_Vertex_num 54   //最大的定点数
#define INFINITY 1000        
typedef int VertexData;      //顶点数据为数字
typedef float WeightType;
typedef WeightType AdjType;

typedef struct ArcNode{
	float adj;
}ArcNode;

typedef struct             //建立一个线性表的结构体
{
	int elem[INFINITY];
	int last;
}SeqList;
typedef SeqList VertexSet;

typedef struct{
	VertexData vexs[Max_Vertex_num];             //设置顶点的矩阵
	ArcNode arcs[Max_Vertex_num][Max_Vertex_num];   //设置边的矩阵
	int vexnum;         //图的顶点数
}AdjMatrix;


void InitList(SeqList *L)  //线性表的初始化
{
	L->elem[0]=0;
	L->last=0;
}           

void AddTail(VertexSet *H,int m)   //在线性表的末尾添加一个结点其值为m
{
	VertexSet *r;
	r=H;
	r->elem[(r->last)+1]=m;
	r->last = r->last+1;
}

void Print(VertexSet *H,AdjMatrix g)
{
	VertexSet *s;
	s = H;
	int i;
	float d=0;
	for(i=1;i<=(s)->last;i++)
	{
		if(s->elem[i]<36)
		{
			printf("%5d  ",(s)->elem[i]);
		}
		else
		{
			printf("    %c  ",(s->elem[i]+29));
		}
	}
	for(i=1;i<s->last;i++)
	{
		d = d + g.arcs[s->elem[i]][s->elem[i+1]].adj;
	}
	printf("\n最短距离为%.2f  \n",d);
	printf("最短的往返时间为:%.2f\n\n",(2*d)/35);
}

int Member(int k,VertexSet *H)
{
	int r = 0;
	VertexSet *p;
	p = H;
	for( int i=1;i<=(p)->last;i++)
	{
		if((p)->elem[i]==k)
		{
			r=1;
			break;
		}
	}
	return r;
}

void ShortestPath_DJS(AdjMatrix g,int v0,WeightType dist[Max_Vertex_num],VertexSet path[Max_Vertex_num])  
   //path[i]中存放顶点i的当前最短路径，dist[i]中存放顶点i的当前最短路径长度
{
	VertexSet s;
	int i,t,k;
	float min;
	for(i=1;i<g.vexnum;i++)
	{
		InitList(&path[i]);   //初始化
		dist[i] = g.arcs[v0][i].adj;
		if(dist[i]<INFINITY && (dist[i]!=0))
		{
			AddTail(&path[i],g.vexs[v0]);
			AddTail(&path[i],g.vexs[i]);
		}
	}
	InitList(&s);     //初始化
	AddTail(&s,g.vexs[v0]);
	for(t=1;t<g.vexnum-1;t++)
	{
		min = INFINITY;
		for(i=1;i<g.vexnum;i++)
		{
			if(!Member(g.vexs[i],&s) && dist[i]<min)
			{
				k =i;
				min = dist[i];
			}
		}
		AddTail(&s,g.vexs[k]);
		for(i=1;i<g.vexnum;i++)
		{
			if(!Member(g.vexs[i],&s) && g.arcs[k][i].adj!= INFINITY &&(dist[k] + g.arcs[k][i].adj<dist[i]) )
			{
				dist[i] = dist[k] + g.arcs[k][i].adj;
				path[i] = path[k] ;
				AddTail(&path[i],g.vexs[i]);
			}
		}
	}
	printf("各条路线为：\n");
	for(i=1;i<g.vexnum;i++)
	{
		if(i<36)
		{
			printf("这是到 %d 结点的最短路线:\n",i);
		}
		else
		{
			printf("这是到 %c 结点的最短路线:\n",(i+29));
		}
		Print(&path[i], g);
	}
	printf("全部的最短路径已经输出\n");
}

void main()
{
	FILE *fp;
	AdjMatrix AdjMatrix;
	fp = fopen("xiao.txt","r");
	int i,j;
	for(i=1;i<Max_Vertex_num;i++)
	{
		for(j=1;j<Max_Vertex_num;j++)
		{
			fscanf(fp,"%f", &AdjMatrix.arcs[i][j]);
		}
	}
	for(i=1;i<Max_Vertex_num;i++)
	{
		AdjMatrix.vexs[i]=i;       //对应的顶点的矩阵的坐标
	}
	AdjMatrix.vexnum = Max_Vertex_num;
	int k;
	char str[2];
	printf("请输入结点的位置:");
	scanf("%s",str);
	k = atoi(str);        //将字符转化为整数
	if(k>-1&&k<36)
	{
		if(k==0)
		{
			k = str[0];
			if(k>96)
			{
				k = k-61;
			}
			else if(k<92 && k>64)
			{
				k = k-29;
			}
			else
			{
				printf("         此节点不存在!!!\n");
				exit(1);
			}
		}
		VertexSet *p = new VertexSet[Max_Vertex_num];
		float *d = new float[Max_Vertex_num];
		if(k>0 && k<54)
		{
			ShortestPath_DJS(AdjMatrix,k,d,p);
		}
		else
		{
			printf("         此节点不存在!!!\n");
		}
	}
	else
	{
		printf("         此节点不存在!!!\n");
	}
}

以下是程序对应的图：

以下是程序中用到的数据 复制以后保存在 xiao.txt 中 ，用于程序导入数据(53*53 的矩阵)：

0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 10.3
5.9 11.2
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 6
1000 1000
1000
1000 0
4.6 1000
8.3 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 8.2
1000 1000
1000
1000 4.6
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 7.8
8.2 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 0
1000 1000
1000 20.4
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
12.7 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 8.3
1000 1000
0 9.7 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 11.3
1000 1000
1000 1000
1000 1000
1000 1000
11.4 1000
1000 1000
1000 1000
1000 1000
1000 1000
9.7 0 7.3
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 11.8
9.5 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 7.3
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
15.1 7.2
1000 1000
1000 1000
1000 1000
14.5 1000
1000 1000
1000 1000
1000
1000 1000
1000 20.4
1000 1000
1000 0
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 8
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 7.8
5.6 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 0
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
10.6 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 14.2
1000 6.6
1000 1000
13.2 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 0
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
12.2 7.8
10.2 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
0 8.6 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
8.6 1000
16.4 9.8
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
8.6 0 15
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 9.9
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 15
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 8.8
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 0
6.8 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 11.8
1000 1000
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 6.8
0 1000
1000 1000
1000 6.7
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 9.6
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 0
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 8.2
8.2 9.2
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
0 9.3 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 8.1
1000 7.2
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
9.3 0 7.9
1000 1000
1000 6.5
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 5.5
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 7.9
0 1000
9.1 1000
7.6 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 4.1
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
6.7 1000
1000 1000
1000 0
10 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 10.1
1000 1000
1000 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
9.1 10
0 8.9 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 7.9
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
8.9 0 1000
1000 18.8
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 13.2
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 6.5
7.6 1000
1000 1000
0 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 12
8.8 1000
1000 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 0
7.8 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
10.5 1000
10.5 1000
1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 18.8
1000 7.8
0 7.9 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞