(一) 实验内容简介
[问题描述]
给定一个图,设计一个程序,找出一条从某一顶点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);
}
暂无评论