数据结构实验--最短路径问题- Dijkstra算法-- Floyd算法

ゝ一纸荒年。 2024-04-01 19:10 74阅读 0赞

> ## 最短路径问题 ##

> ### Dijkstra算法 ###

*  运行代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    
    const int MaxSize = 10; //图中最多顶点个数
    
    class MGraph
    {
    public:
    	MGraph(string a[], int n, int e); //构造函数，建立具有n个顶点e条边的图
    	~MGraph() { }; //析构函数
    	void Dijkstra(int v);
    private:
    	int Min(int r[], int n);
    	string vertex[MaxSize]; //存放图中顶点的数组
    	int edge[MaxSize][MaxSize]; //存放图中边的数组
    	int vertexNum, edgeNum; //图的顶点数和边数
    };
    
    //构造函数
    MGraph::MGraph(string a[], int n, int e)
    {
    	int i, j, k, w;
    	vertexNum = n; edgeNum = e;
    	for (i = 0; i < vertexNum; i++) //存储顶点
    		vertex[i] = a[i];
    	for (i = 0; i < vertexNum; i++) //初始化邻接矩阵
    		for (j = 0; j < vertexNum; j++)
    			if (i == j)
    				edge[i][j] = 0;
    			else
    				edge[i][j] = 1000; //假设边上权值最大是1000
    	for (k = 0; k < edgeNum; k++) //依次输入每一条边
    	{
    		cout << "请输入边依附的两个顶点的编号，以及边上的权值：";
    		cin >> i >> j >> w; //输入边依附的两个顶点的编号
    		edge[i][j] = w; //置有边标志
    	}
    }
    
    //Dijkstra
    void MGraph::Dijkstra(int v) //从源点v出发
    {
    	int i, k, num, dist[MaxSize];
    	string path[MaxSize];
    	for (i = 0; i < vertexNum; i++) //初始化数组dist和path
    	{
    		dist[i] = edge[v][i];
    		if (dist[i] != 100) //假设100为边上权的最大值
    			path[i] = vertex[v] + vertex[i]; //+为字符串连接操作
    		else path[i] = "";
    	}
    	for (num = 1; num < vertexNum; num++)
    	{
    		k = Min(dist, vertexNum); //在dist数组中找最小值并返回其下标
    		cout << path[k] << ":" << dist[k] << endl;
    		for (i = 0; i < vertexNum; i++) //修改数组dist和path
    			if (dist[i] > dist[k] + edge[k][i]) {
    				dist[i] = dist[k] + edge[k][i];
    				path[i] = path[k] + vertex[i]; //+为字符串连接操作
    			}
    		dist[k] = 0; //将顶点k加到集合S中
    	}
    }
    
    //找最小值
    int MGraph::Min(int r[], int n)
    {
    	int index = 0, min = 100;
    	for (int i = 0; i < n; i++)
    		if (r[i] != 0 && r[i] < min)
    		{
    			min = r[i]; index = i;
    		}
    	return index;
    }
    
    int main()
    {
    	int i;
    	string ch[] = {"A","B","C","D","E"};
    	/* 
    	测试数据使用 图6-20(b)，输入边七条边是：
    	(0 1 10)(0 4 100)(0 3 30)(1 2 50)(2 4 10)(3 2 20)(3 4 60) 
    	*/
    	MGraph MG(ch, 5, 7 ); //建立具有5个顶点6条边的无向图
    	MG.Dijkstra(0);
    	return 0;
    }

> 运行结果：

![f8c14f4e5f63427197326d27534ad270.png][]

> ### Floyd算法 ###

*  运行代码：

/*
    *	Floyd算法
    */
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int MaxSize = 10;                   //图中最多顶点个数
    
    class MGraph
    {
    public:
    	MGraph(string a[], int n, int e);     //构造函数，建立具有n个顶点e条边的图
    	~MGraph() { };                        //析构函数
    	void Floyd();
    private:
    	string vertex[MaxSize];           //存放图中顶点的数组
    	int edge[MaxSize][MaxSize];           //存放图中边的数组
    	int vertexNum, edgeNum;              //图的顶点数和边数
    };
    
    MGraph::MGraph(string a[], int n, int e)
    {
    	int i, j, k, w;
    	vertexNum = n; edgeNum = e;
    	for (i = 0; i < vertexNum; i++)          //存储顶点
    		vertex[i] = a[i];
    	for (i = 0; i < vertexNum; i++)          //初始化邻接矩阵
    		for (j = 0; j < vertexNum; j++)
    			if (i == j)
    				edge[i][j] = 0;
    			else
    				edge[i][j] = 1000;            //假设边上权值最大是1000 
    	for (k = 0; k < edgeNum; k++)           //依次输入每一条边
    	{
    		cout << "请输入边依附的两个顶点的编号，以及边上的权值：";
    		cin >> i >> j >> w;                       //输入边依附的两个顶点的编号
    		edge[i][j] = w;                           //置有边标志
    	}
    }
    
    void MGraph::Floyd()
    {
    	int i, j, k, dist[MaxSize][MaxSize];
    	string path[MaxSize][MaxSize];
    	for (i = 0; i < vertexNum; i++)              //初始化矩阵dist和path
    		for (j = 0; j < vertexNum; j++)
    		{
    			dist[i][j] = edge[i][j];
    			if (dist[i][j] != 1000)                 //假设100为边上权的最大值
    				path[i][j] = vertex[i] + vertex[j];     //+为字符串连接操作
    			else path[i][j] = "";
    		}
    	for (k = 0; k < vertexNum; k++)                //进行n次迭代
    		for (i = 0; i < vertexNum; i++)
    			for (j = 0; j < vertexNum; j++)
    				if (dist[i][k] + dist[k][j] < dist[i][j]) {
    					dist[i][j] = dist[i][k] + dist[k][j];
    					path[i][j] = path[i][k] + path[k][j];    //+为字符串连接操作
    				}
    	for (i = 0; i < vertexNum; i++)
    	{
    		for (j = 0; j < vertexNum; j++)
    			cout << path[i][j] << ":" << dist[i][j] << "\t";
    		cout << endl;
    	}
    }
    
    int main()
    {
    	int i;
    	string ch[] = { "A","B","C" };
    	/* 
    		测试数据使用 图6-24，输入边五条边是：
    		(0 1 4)(0 2 1)(1 0 6)(1 2 2)(2 3 3) 
    	*/
    	MGraph MG{ ch, 3, 5 };    //建立具有5个顶点6条边的无向图
    	MG.Floyd();
    	return 0;
    }

> 运行结果：

![7e97d61000b247539eae15e54cca96b1.png][]

[f8c14f4e5f63427197326d27534ad270.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/419891d6d0e24a569b247fd4ab00c40a.png
[7e97d61000b247539eae15e54cca96b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4ed8b1ccc4d44852b5f1175a2b0876a8.png