大二数据结构实验（迪杰斯特拉最短路径）-Toy模板网

这篇具有很好参考价值的文章主要介绍了大二数据结构实验（迪杰斯特拉最短路径）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大二数据结构实验，有详细批注，代码可以直接运行，希望可以给大家提供到帮助。

实验目的

掌握图的邻接矩阵的存储定义。
掌握图的最短路径（Dijsktra）算法的实现。

实验内容

设计校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。

从文件graph.txt中读取相应数据, 创建一个图,使用邻接矩阵表示图（算法6.1）。
景点信息查询：为来访客人提供校园任意景点相关信息的介绍。
问路查询：为来访客人提供校园任意两个景点之间的一条最短路径（算法6.10）。

graph.txt：
大二数据结构实验（迪杰斯特拉最短路径）,数据结构,算法,图论

程序核心代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2


#define MAXVEX 8   //最大顶点数
#define INFINITY 65535   //用65535来代表∞
typedef int Patharc[MAXVEX];  //用于存储最短路径下标
typedef int ShortPathTable[MAXVEX];   //同于存储到各点最短路径权值
typedef int EdgeType;   //边上的权值类型
int o;
typedef struct
{
	int n;
	char name[100];
	char info[10000];
}VertexType;          //顶点类型
typedef struct
{
	VertexType vexs[MAXVEX];    //顶点表
	EdgeType arc[MAXVEX][MAXVEX];   //邻接矩阵
	int numVertexes, numEdges;
}MGraph;

//邻接矩阵(无向图)
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	FILE* fp;
	//printf("输入定点数和边数：\n");
	fp = fopen("C://Users//86133//Desktop//graph.txt", "r");
	if (fp == NULL)
	{
		printf("无法发现文件");
		exit(0);
	}
	fscanf(fp, "%d\n", &G->numVertexes);
	fscanf(fp, "%d\n", &G->numEdges);
	for (i = 0; i < G->numVertexes; i++)   //读入顶点信息
	{
		fscanf(fp, "%s\n", G->vexs[i].name);
		fscanf(fp, "%s\n", G->vexs[i].info);
		G->vexs[i].n = i;
	}
	for (i = 0; i < G->numVertexes; i++)   //读入顶点信息
	{
		printf("%s   %s\n", G->vexs[i].info, G->vexs[i].name);
	}

	for (i = 0; i < G->numVertexes; i++)   //初始化
	{
		for (j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j] = INFINITY;
		}
	}
	for (k = 0; k < G->numEdges; k++)
	{
		//printf("输入边（vi,vj）上的下标i，下标j和权w：\n");
		fscanf(fp, "%d %d %d", &i, &j, &w);
		G->arc[i][j] = w;
		G->arc[j][i] = G->arc[i][j];   //因为是无向图，所以矩阵对称
	}
	for (i = 0; i < G->numVertexes; i++)   //初始化
	{
		for (j = 0; j < G->numVertexes; j++)
		{
			printf("%d   ", G->arc[i][j]);
		}
		printf("\n");
	}
	fclose(fp);
}


void ShortestPath(MGraph G, int V0, Patharc* P, ShortPathTable* D)
{
	int v, w, k, min;
	int s1, s2;
	int final[MAXVEX];		// final[w] = 1 表示已经求得顶点V0到Vw的最短路径

	// 初始化数据
	for (v = 0; v < G.numVertexes; v++)
	{
		final[v] = 0;				// 全部顶点初始化为未找到最短路径
		(*D)[v] = G.arc[V0][v];		// 将与V0点有连线的顶点加上权值
		(*P)[v] = 0;				// 初始化路径数组P为0
	}
	(*D)[V0] = 0;		// V0至V0的路径为0
	final[V0] = 1;		// V0至V0不需要求路径

	// 开始主循环，每次求得V0到某个V顶点的最短路径
	for (v = 1; v < G.numVertexes; v++)
	{
		min = INFINITY;
		for (w = 0; w < G.numVertexes; w++)
		{
			if (!final[w] && (*D)[w] < min)
			{
				k = w;
				min = (*D)[w];
			}
		}
		final[k] = 1;	// 将目前找到的最近的顶点置1

		// 修正当前最短路径及距离
		for (w = 0; w < G.numVertexes; w++)
		{
			// 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
			if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
			{
				(*D)[w] = min + G.arc[k][w];	// 修改当前路径长度
				(*P)[w] = k;					// 存放前驱顶点
			}
		}
	}
	printf("最短路径为：");
	printf("%d\n", (*D)[o]);
	printf("最短路程为：");
	s1 = o;
	while (s1 != V0)
	{
		printf("%s   ", G.vexs[s1].name);
		s1 = (*P)[s1];
	}
	printf("%s", G.vexs[V0].name);
	printf("\n");
}
int main()
{
	int v;
	int r;
	MGraph G;
	Patharc A;
	ShortPathTable B;
	printf("创建图完成\n");
	printf("景点以及它的信息为\n");
	CreateMGraph(&G);
	while (TRUE)
	{
		printf("从西和出发");
		while (TRUE)
		{
			v = 0;
			if (v > MAXVEX || v < 0)
			{
				printf("请重新输入\n");
				continue;
			}
			break;
		}
		printf("请输入终点");
		while (TRUE)
		{
			scanf("%d", &o);
			if (v > MAXVEX || v < 0)
			{
				printf("请重新输入\n");
				continue;
			}
			break;
		}
		ShortestPath(G, v, &A, &B);
		printf("如须结束则输入0,如继续则输入任意数字\n");
		scanf("%d", &r);
		if (r == 0)
			break;
	}
	return 0;
}