多段图的动态规划算法（C/C++）-Toy模板网

这篇具有很好参考价值的文章主要介绍了多段图的动态规划算法（C/C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 实验环境

（1）Visual Studio 2019（32位调试器）

（2）Windows 10

2. 多段图描述

多段图G = (V,E)是一个带权有向图，它具有以下特性：

图中的节点被划分成K>=2个互不相交的子集Vi, 1<=i<=k。其中V1和Vk分别只有一个节点，V1包含源点s,Vk包含汇点t。对所有边<u,v>∈E，多段图要求若u∈Vi，则v∈V(i+1)（1<=i<k），边上的权值位w（u，v）。从s到t的路径长度是这条路径上边的权值之和。

多段图问题，是求从s到t的一条长度最短的路径。

多段图的动态规划算法（C/C++）

3. 算法的具体实现

定义了cost[ ]和d[ ]，cost[ i ]用于存储到从节点 i 到汇点(t)的最短权值之和； d[ i ]用于存储 i 节点所指向的权值最小的节点，如上图中：

cost[10] = 5, d[10] = 11

cost[9] = 2, d[9] = 11

cost[8] = 4, d[8] = 11

cost[7] = 7, d[7] = 9

cost[6] = 5, d[6] = 9

cost[5] = 7, d[5] = 9

cost[4] = 15, d[4] = 7

cost[3] = 18, d[3] = 7

cost[2] = 9, d[2] = 5

cost[1] = 7, d[1] = 6

cost[0] = 16, d[0] = 2

所以算法执行结束cost[ 0 ]，即为源点--->汇点的最短路径。

多段图的动态规划算法

传入参数node为节点个数，G为引用图的数据结构

float FMultiGraph(ALGraph& G, int node) {
	float* cost = new float[node];
	int q, * d = new int[node];
	cost[node - 1] = 0;
	d[node - 1] = -1;
	for (int i = node-2; i >= 0; --i)
	{
		float min = 65535;
		for (ArcNode *p = G.adjlist[i].FirstArc ; p; p=p->nextArc)
		{
			int v = p->adjvex;
			if ((p->weight + cost[v]) < min)
			{
				min = p->weight + cost[v];
				q = v;
			}
		}
		cost[i] = min;
		d[i] = q;
	}
	float c = cost[0];
	return c;
}

图的邻接表结构定义

//定义临界表边结点
typedef struct ArcNode
{
	int adjvex;
	int weight;		//权值
	struct ArcNode* nextArc;
}ArcNode;

//定义临界表表头结点
typedef struct VertexNode
{
	int vertex;
	int jieduan;	//阶段
	ArcNode* FirstArc;
}VertexNode;

//定义图的临接表类型
typedef struct ALGraph
{
	VertexNode adjlist[max];    //max define为100
}ALGraph;

图的邻接表创建

void creatGraph(ALGraph &G, int node,int edge){
	//初始化多少个图节点 以及图各节点的名称
	for (int i = 0; i < node; i++)
	{
		int NodeName = 0, jieduan = 0;
		cin >> NodeName >> jieduan;
		G.adjlist[i].vertex = NodeName;
		G.adjlist[i].jieduan = jieduan;
		G.adjlist[i].FirstArc = NULL;
	}

	for (int i = 0; i < edge; i++)
	{
		int from = 0, to = 0, weight = 0;	//从 from 节点开始到 to节点  权值为 weight
		cin >> from >> to >> weight;
		ArcNode* p = new ArcNode;	
		p->adjvex = to; 
		p->weight = weight;
		p->nextArc = G.adjlist[from].FirstArc;
		G.adjlist[from].FirstArc = p;
	}
}

图的打印

void printfGraph(ALGraph& G, int node) {
	for (int i = 0; i < node; i++)
	{
		cout << "V" << G.adjlist[i].jieduan << ": " << G.adjlist[i].vertex << " -> ";
		ArcNode* temp =  G.adjlist[i].FirstArc;
		while (temp)
		{
			cout << temp->adjvex << "(" << temp->weight << ") -> ";
			temp = temp->nextArc;
		}
		cout << "NULL" << endl;
	}
}

主函数如下

int main() {

	ALGraph G;
	int node = 0, edge = 0;
	cin >> node >> edge;
	creatGraph(G, node, edge);
	printfGraph(G, node);

	float lujing = FMultiGraph(G, node);

	cout << "最短路径为：" << lujing << endl;
	system("pause");
	return 0;
}

4. 测试数据输入及输出

使用测试数据输入如下（使用文件重定向将数据写入文件再使用）使用方法如下

打开多段图的动态规划算法（C/C++）