数据结构——图论距离算法

发布于 2020-04-14  101 次阅读


(一)         实验内容简介

[问题描述]

给定一个图,设计一个程序,找出一条从某一顶点A到另一顶点B边数最少的一条路径。

[输入]

图的顶点个数N,图中顶点之间的边的关系及要找的路径的起点A和终点B。

[输出]

若A到B无路径,则输出“There is no path”,否则输出A到B路径上各顶点。

[存储结构]

图采用邻接矩阵或邻接表的方式存储。

(二)         程序设计思路

首先根据题目,中心是根据图寻找最低路径的问题,显然我们可以用dijkstra算法来实现。

把问题分为三部分,创建图的数据结构,寻找最短路径,显示最短路径。

创建图的数据结构可以使用邻接矩阵实现,寻找最短路径使用dijkstra算法实现,显示最短路径则根据特性,使用递归实现。

(三)         算法分析与设计

中心算法是dijkstra算法。

算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3),直到遍历完所有顶点。

(四)         数据结构设计

使用邻接矩阵实现,邻接矩阵的结构如下:

typedef struct
{
	int N;//顶点编号
	char name;//顶点信息
}ver;
typedef struct
{
	int adjmat[MAX][MAX];//邻接矩阵
	int v;//点个数
	int e;//边个数
	ver ver[MAX];//顶点数组
}matgraph;

(五)         系统实现(系统架构,操作系统运用,数据库运用等)

本实验中未使用系统实现

(六)         测试结果

使用图为

测试成功。

(七)         源代码

#include <errno.h>
#include <string.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include<string>
#include <stack>
#include <vector>
#include <deque>
#include<stdlib.h>
#include <algorithm>
#pragma warning (disable: 4996)
using namespace std;
#define MAX 5
#define LIMT 99999
typedef struct
{
	int N;//顶点编号
	char name;//顶点信息
}ver;
typedef struct
{
	int adjmat[MAX][MAX];//邻接矩阵
	int v;//点个数
	int e;//边个数
	ver ver[MAX];//顶点数组
}matgraph;
void creat(matgraph*& G, int A[MAX][MAX], int v, int e)
{
	int i, j;
	G = (matgraph*)malloc(sizeof(matgraph));
	for (i = 0; i < v; i++) {
		G->ver[i].N = i;
		G->ver[i].name = 'A' + i;
	}
	for (i = 0; i < v; i++) for (j = v - 1; j >= 0; j--)G->adjmat[i][j] = A[i][j];
	G->e = e;
	G->v = v;
}
void Ppath(int path[], int i, int v) //前向递归查找路径上的顶点
{
	int k;
	k = path[i];
	if (k == v)
	{
		return;
	}
	Ppath(path, k, v);
	printf("%d", k);
}
void Dispath(int dist[], int path[], int s[], int n, int v)
{
	int i;
	for (i = 0; i < n; i++)
	{
		if (s[i] == 1)
		{
			printf("从%d到%d的最短路径长度为:%d\t路径为:", v, i, dist[i]);
			printf("%d", v);//输出路径上的起点
			Ppath(path, i, v); //输出路径上的中间点
			printf("%d\n", i);//输出路径上的终点
		}
		else
		{

			printf("从%d到%d不存在路径\n", v, i);
		}
	}
}
void dijkstra(matgraph* G, int v)
{
	int mindis, i, j, u;
	int s[MAX];
	int dist[MAX];
	int path[MAX];
	for (i = 0; i < G->v; i++) {
		s[i] = 0;
		dist[i] = G->adjmat[v][i];
		if (G->adjmat[v][i] < LIMT)
			path[i] = v;
		else
			path[i] = -1;
	}
	s[v] = 1;
	path[v] = 0;
	for (i = 0; i < G->v; i++) {
		mindis = LIMT;
		for (j = 0; j < G->v; j++) {
			if (s[j] == 0 && dist[j < mindis]) {
				mindis = dist[j];
				u = j;
			}
		}
		s[u] = 1;
		for (j = 0; j < G->v; j++) {
			if (s[j] == 0) {
				if (G->adjmat[u][j] < LIMT && dist[u] + G->adjmat[u][j] < dist[j]) {
					dist[j] = dist[u] + G->adjmat[u][j];
					path[j] = u;
				}
			}
		}
	}
	Dispath(dist, path, s, G->v, v);
}
void dispmat(matgraph* G)  //图的邻接矩阵存储方式输出
{
	int i, j;
	printf("\n图的邻接矩阵存储\n");
	for (i = 0; i < G->v; i++)
	{
		printf("编号%d的顶点%c:", G->ver[i].N, G->ver[i].name);
		for (j = 0; j < G->v; j++)
			printf("%d ", G->adjmat[i][j]);  //没有权,这里的链表只输出邻接顶点编号
		printf("\n");
	}
}
int main()
{
	int adj_mat[MAX][MAX] =
	{								//图的形状:
		{0,2,LIMT,4,LIMT},			//        B
		{LIMT,0,2,3,LIMT},			//     2↙↓3↖2
		{LIMT,LIMT,0,1,2},			//    C→1 D←4A
		{LIMT,LIMT,LIMT,0,LIMT},    //     ↘2↑1↗5
		{5,LIMT,LIMT,1,0}			//        E
	};
	int v = 5, e = 8;
	matgraph* G = NULL;
	creat(G, adj_mat, v, e);
	dijkstra(G, 0);
}

山下闲人漫步,山上泉水熙熙。 山外庸人自扰,山里野花灿灿。