(一)         实验内容简介

[问题描述]

给定一个图，设计一个程序，找出一条从某一顶点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);
}