通信软件基础实验03

2022-10-13

字数统计: 3.4k | 阅读时长≈ 15 分钟

写在前面

本次通信软件基础实验运用上了数据结构——图，并且用了Dijkstra算法，有相当的难度（对我个人来说），因为这次实验是小组作业，所以没有单独的实验报告，以下内容会按前几次报告的格式来写。

一. 引言

图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。
邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设 G=(V,E)是一个图，其中 V={v1,v2,…,vn}。G 的邻接矩阵是一个具有下列性质的 n 阶方阵：

① 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为 0，有向图则不一定如此。

② 在无向图中，任一顶点 i 的度为第 i 列（或第 i 行）所有非零元素的个数，在有向图中顶点 i 的出度为第 i 行所有非零元素的个数，而入度为第 i 列所有非零元素的个数。

③ 用邻接矩阵法表示图共需要 n^2 个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要 n（n-1）/2 个空间。

本次实验使用的是邻接矩阵
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

二. 实验要求

给定任意带权重的连通图形，求出指定起点到所有点的最短路径和最短路径的长度，并打印出经过的路径及最短路径长度。
请把图形转化为数据，并通过文本/手动输入。

三. 设计思路与方案

1.流程图

（之前画的流程图好像都是错的….ヾ(･ε･｀*) 不重要了）

2.全局变量及结构体：

#define MAXVEX 20//最大顶点数
#define GRAPH_INFINTY 32767//无限，表未连接

struct Graph//图结构体
{
    char city_name[MAXVEX][20];//记录节点名称
    int arc[MAXVEX][MAXVEX];//邻接矩阵
    int vex_num;//顶点数
};

3.各类函数：

图初始化函数

通过读取文件，对图进行初始化

void CreateGraph(struct Graph *G)//读取文件生成图函数
{
	FILE* fp;
    int X, Y, W;//行，列，权值
	if ((fp = fopen("Dijkstra_input.txt", "r")) == NULL)//打开文件
	{
		printf("打开文件错误");
		return;
	}
    fscanf(fp, "节点个数：");//跳过
	fscanf(fp, "%d", &G->vex_num);//写入节点个数
    printf("节点个数： % d\n", G->vex_num);
    fscanf(fp, "节点名称：");//跳过
    for (int i = 0; i < G->vex_num; i++)
    {
        fscanf(fp, "%s", G->city_name[i]);
        printf("节点%d：%s\n",i+1, G->city_name[i]);
    }

    for (int i = 0; i < G->vex_num; i++)//对图赋初值
    {
        for (int j = 0; j < G->vex_num; j++)
        {
            G->arc[i][j] = GRAPH_INFINTY;//初始皆为断开
        }
		G->arc[i][i] = 0;//无自环
    }
    printf("\n已有边关系：\n");
    for (int i = 0;; i++)//读取文件获取边
    {
        if (fscanf(fp, "%d %d %d", &X, &Y, &W) == EOF)
            break;
        else
        {
            //无向图邻接矩阵对称
            G->arc[X-1][Y-1] = W;
            G->arc[Y-1][X-1] = W;
            printf("节点\"%s\"-节点\"%s\"路径长度：%d\n",G->city_name[X - 1],G->city_name[Y - 1], W);
        }
    }
}

最短路径判断函数（Dijkstra算法辅助函数1）

判断后继节点是否为最短路径的必经节点，并对路径进行更新

int getMin(int* d, int* s, struct Graph* G) //获取最短路径
{
    int min = GRAPH_INFINTY;
    int index;
    for (int i = 0; i < G->vex_num; i++) 
    {
        if (s[i] == 0 && d[i] < min)//未确定节点最短路径且当前路径小于已有路径长度最小值 
        {
            //更新min与索引
            min = d[i];
            index = i;
        }
    }
    return index;
}

Dijkstra算法信息输出函数（Dijkstra算法辅助函数2）

打印通过Dijkstra算法获取的源节点到各节点的最短路径信息

void printDijkstra(int cityNow, int* s, int* p, int* d, struct Graph* G)//输出源节点到各节点的最短路径信息
{
    int* fd = (int*)malloc(sizeof(int) * G->vex_num);//生成动态数组，保存下标序列，便于输出信息
    int pos;//哨兵，记录当前位置前驱
    printf("\n节点%d%s",cityNow+1, G->city_name[cityNow]);
    printf("到各节点信息：\n");
    for (int i = 0; i < G->vex_num; i++)
    {
        if (i == cityNow)//忽略自环
            continue;
        pos = p[i];//记录前驱
        printf("节点\"%s\"-节点\"%s\"最短路径长度：%d\n路径：", G->city_name[cityNow], G->city_name[i], d[i]);
        for (int j = 0; j < G->vex_num; j++)
        {
            fd[j] = pos;//将前驱写入序列
            pos = p[pos];//更新位置，写入新的前驱
            if (pos == -1)//到源节点时进行输出
            {
                for (; j >= 0; j--)//将路径正序输出
                {
                    printf("%s->", G->city_name[fd[j]]);
                }
                printf("%s\n", G->city_name[i]);
                break;
            }   
        }
    }
}

Dijkstra算法核心函数

Dijkstra算法核心

void Dijkstra(struct Graph* G, int index)//Dijkstra算法核心 
{
    // 准备辅助数组
    int* s = (int*)malloc(sizeof(int) * G->vex_num);//s数组记录是否找到对应节点最短路径，1-找到、0未找到
    int* p = (int*)malloc(sizeof(int) * G->vex_num);//p数组记录当前节点的前驱节点
    int* d = (int*)malloc(sizeof(int) * G->vex_num);//d数组记录最初节点到当前节点的路径长度
    int cityNow = index;//保存源节点位置
    // 初始化辅助数组
    for (int i = 0; i < G->vex_num; i++) 
    {
        if (G->arc[index][i] > 0 && G->arc[index][i] != GRAPH_INFINTY)//非自身且非断路
        {
            d[i] = G->arc[index][i];//初始化路径长度
            p[i] = index;//初始化前驱
        }
        else 
        {
            d[i] = GRAPH_INFINTY;
            p[i] = -1;//-1表示无节点
        }
        if (i == index) 
        {
            s[i] = 1;//源节点极为最近路径必经节点，赋1
            d[i] = 0;//路径长度0
        }
        else
            s[i] = 0;//其余节点为确定最短路径赋0
    }
    //寻找到各节点的最短路径
    for (int i = 0; i < G->vex_num - 1; i++) 
    {
        index = getMin(d, s, G);
        s[index] = 1;//找到当前节点的最短路径
        for (int j = 0; j < G->vex_num; j++) 
        {
            if (s[j] == 0 && d[index] + G->arc[index][j] < d[j])//未找到最短路径且当前路径长度小于已有路径，更新信息 
            {
                d[j] = d[index] + G->arc[index][j];//更新路径长度
                p[j] = index;//记录前驱
            }
        }
    }
    /*//检测算法，调试用
    for (int i = 0; i < G->vex_num; i++)
    {
        printf("%d %d %d\n", s[i], p[i], d[i]);
    }
    */
    printDijkstra(cityNow,s,p, d, G);
}

主函数

调用各类函数，对所求路径进行输入

void main()
{
    int index;//索引
    struct Graph G;//生成图
    CreateGraph(&G);//初始化图
    while (1)
    {
        printf("\n请输入求最短路径的节点：");
        scanf("%d", &index);
        if ((index - 1 < G.vex_num) && (index > 0))
            break;
        else
            printf("输入错误\n");
    }
    Dijkstra(&G, index - 1);
}

4.整体代码

/*
IDE:Visual Studio 2022
字符集:Unicode
文本文档编码：ANSI
SDL检查：否
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXVEX 20//最大顶点数
#define GRAPH_INFINTY 32767//无限，表未连接


struct Graph//图结构体
{
    char city_name[MAXVEX][20];//记录节点名称
    int arc[MAXVEX][MAXVEX];//邻接矩阵
    int vex_num;//顶点数
};

void CreateGraph(struct Graph *G)//读取文件生成图函数
{
	FILE* fp;
    int X, Y, W;//行，列，权值
	if ((fp = fopen("Dijkstra_input.txt", "r")) == NULL)//打开文件
	{
		printf("打开文件错误");
		return;
	}
    fscanf(fp, "节点个数：");//跳过
	fscanf(fp, "%d", &G->vex_num);//写入节点个数
    printf("节点个数： % d\n", G->vex_num);
    fscanf(fp, "节点名称：");//跳过
    for (int i = 0; i < G->vex_num; i++)
    {
        fscanf(fp, "%s", G->city_name[i]);
        printf("节点%d：%s\n",i+1, G->city_name[i]);
    }

    for (int i = 0; i < G->vex_num; i++)//对图赋初值
    {
        for (int j = 0; j < G->vex_num; j++)
        {
            G->arc[i][j] = GRAPH_INFINTY;//初始皆为断开
        }
		G->arc[i][i] = 0;//无自环
    }
    printf("\n已有边关系：\n");
    for (int i = 0;; i++)//读取文件获取边
    {
        if (fscanf(fp, "%d %d %d", &X, &Y, &W) == EOF)
            break;
        else
        {
            //无向图邻接矩阵对称
            G->arc[X-1][Y-1] = W;
            G->arc[Y-1][X-1] = W;
            printf("节点\"%s\"-节点\"%s\"路径长度：%d\n",G->city_name[X - 1],G->city_name[Y - 1], W);
        }
    }
}

int getMin(int* d, int* s, struct Graph* G) //获取最短路径
{
    int min = GRAPH_INFINTY;
    int index;
    for (int i = 0; i < G->vex_num; i++) 
    {
        if (s[i] == 0 && d[i] < min)//未确定节点最短路径且当前路径小于已有路径长度最小值 
        {
            //更新min与索引
            min = d[i];
            index = i;
        }
    }
    return index;
}

void printDijkstra(int cityNow, int* s, int* p, int* d, struct Graph* G)//输出源节点到各节点的最短路径信息
{
    int* fd = (int*)malloc(sizeof(int) * G->vex_num);//生成动态数组，保存下标序列，便于输出信息
    int pos;//哨兵，记录当前位置前驱
    printf("\n节点%d%s",cityNow+1, G->city_name[cityNow]);
    printf("到各节点信息：\n");
    for (int i = 0; i < G->vex_num; i++)
    {
        if (i == cityNow)//忽略自环
            continue;
        pos = p[i];//记录前驱
        printf("节点\"%s\"-节点\"%s\"最短路径长度：%d\n路径：", G->city_name[cityNow], G->city_name[i], d[i]);
        for (int j = 0; j < G->vex_num; j++)
        {
            fd[j] = pos;//将前驱写入序列
            pos = p[pos];//更新位置，写入新的前驱
            if (pos == -1)//到源节点时进行输出
            {
                for (; j >= 0; j--)//将路径正序输出
                {
                    printf("%s->", G->city_name[fd[j]]);
                }
                printf("%s\n", G->city_name[i]);
                break;
            }   
        }
    }
}

void Dijkstra(struct Graph* G, int index)//Dijkstra算法核心 
{
    // 准备辅助数组
    int* s = (int*)malloc(sizeof(int) * G->vex_num);//s数组记录是否找到对应节点最短路径，1-找到、0未找到
    int* p = (int*)malloc(sizeof(int) * G->vex_num);//p数组记录当前节点的前驱节点
    int* d = (int*)malloc(sizeof(int) * G->vex_num);//d数组记录最初节点到当前节点的路径长度
    int cityNow = index;//保存源节点位置
    // 初始化辅助数组
    for (int i = 0; i < G->vex_num; i++) 
    {
        if (G->arc[index][i] > 0 && G->arc[index][i] != GRAPH_INFINTY)//非自身且非断路
        {
            d[i] = G->arc[index][i];//初始化路径长度
            p[i] = index;//初始化前驱
        }
        else 
        {
            d[i] = GRAPH_INFINTY;
            p[i] = -1;//-1表示无节点
        }
        if (i == index) 
        {
            s[i] = 1;//源节点极为最近路径必经节点，赋1
            d[i] = 0;//路径长度0
        }
        else
            s[i] = 0;//其余节点为确定最短路径赋0
    }
    //寻找到各节点的最短路径
    for (int i = 0; i < G->vex_num - 1; i++) 
    {
        index = getMin(d, s, G);
        s[index] = 1;//找到当前节点的最短路径
        for (int j = 0; j < G->vex_num; j++) 
        {
            if (s[j] == 0 && d[index] + G->arc[index][j] < d[j])//未找到最短路径且当前路径长度小于已有路径，更新信息 
            {
                d[j] = d[index] + G->arc[index][j];//更新路径长度
                p[j] = index;//记录前驱
            }
        }
    }
    /*//检测算法，调试用
    for (int i = 0; i < G->vex_num; i++)
    {
        printf("%d %d %d\n", s[i], p[i], d[i]);
    }
    */
    printDijkstra(cityNow,s,p, d, G);
}



void main()
{
    int index;//索引
    struct Graph G;//生成图
    CreateGraph(&G);//初始化图
    while (1)
    {
        printf("\n请输入求最短路径的节点：");
        scanf("%d", &index);
        if ((index - 1 < G.vex_num) && (index > 0))
            break;
        else
            printf("输入错误\n");
    }
    Dijkstra(&G, index - 1);
}

四. 调试

在读取文件时，打印出的中文乱码，更改TXT文档编码为ANSI问题解决。

在对图进行初始化时最初使用的无限变量太大，无法写入发生报错，改小后问题解决。

五. 附录

结果展示

六. 相关资源

【算法】最短路径查找—Dijkstra算法

数据结构-最短路径dijkstra(迪杰斯特拉)算法-C语言实现

实验数据（Dijkstra_input.txt）

节点个数：8
重庆北京成都上海深圳杭州广州武汉
1 2 24
1 3 47
1 4 70
2 3 25
2 5 120
3 4 23
3 5 88
3 6 66
4 6 31
4 7 42
5 6 31
5 8 29
6 7 74
6 8 79
7 8 66

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！