天天看点
返回

动态规划之Floyd算法；

如题；这是一套完整的可运行的代码；需要读者有一定的基础去阅读；

语言是用C语言实现；在C++环境中编写；在C++中可直接运行；在C语言中需要改部分头文件和输出语句；

头文件；这要是代码的声明部分；

Prim算法， Kruskal算法， Dijkstra算法， Floyd算法中；只有Floyd算法是动态规划(Dynamic Programming);

其他的三个都是贪心算法（Greedy algorithm）;如果需要对算法有更深刻的理解；就要学习动态规划；精髓是解决问题的思想；将复杂的问题划分为小问题求解；

# ifndef _AMGRAPH_
# define _AMGRAPH_

# include <iostream>
using namespace std;

# define MaxVertexNum 256
typedef char VertexType;
typedef int EdgeType;

typedef struct
{
	VertexType vertex[MaxVertexNum];
	EdgeType edge[MaxVertexNum][MaxVertexNum];
	int vertexNum;
	int edgeNum;
}AMGraph, * PAMGraph;

int LocateVertex(PAMGraph g, VertexType x);
PAMGraph CreateGraph(void);

void BFS(PAMGraph g, int i);
void BFSTraversal(PAMGraph g);

# define INFINITY 10000
typedef struct
{
	int adjvertex;
	int lowcost;
}AuxArray;

void MiniSpanTreePrim(PAMGraph g, int i);

void ShortestPathDij(PAMGraph g, int u, int * D, int * P);

void ShortestPathFloyd(PAMGraph g, int ** D, int ** P);

//void Show(int i, int j, int ** D, int ** P);

# endif

实现文件；主要是代码的实现；

# include "AMGraph.h"
# include "SeqQueue.h"

bool visited[MaxVertexNum] = { 0 };

int LocateVertex(PAMGraph g, VertexType x)
{
	int i = 0;

	while ((i < g->vertexNum) && (g->vertex[i] != x))
	{
		i += 1;
	}

	if (i >= g->vertexNum)
	{
		return -1;
	}
	else
	{
		return i;
	}
}

PAMGraph CreateGraph(void)
{
	PAMGraph g = (PAMGraph)malloc(sizeof(AMGraph));

	if (NULL != g)
	{
		//输入顶点数和边数；
		cout << "Please input the vertexNum and edgeNum: " << endl;
		cin >> g->vertexNum >> g->edgeNum;

		//输入顶点值；
		for (int i = 0; i < g->vertexNum; i++)
		{
			cout << "Please input the element value: " << endl;
			cin >> g->vertex[i];
		}

		//输入边节点的值；
		for (int i = 0; i < g->vertexNum; i++)
		{
			for (int j = 0; j < g->vertexNum; j++)
			{
				if (i == j)
				{
					g->edge[i][j] = 0;
				}
				else
				{
					g->edge[i][j] = INFINITY;
				}
			}
		}

		int i = 0;
		int j = 0;
		for (int k = 0; k < g->edgeNum; k++)
		{
			cout << "Please input the two index: " << endl;
			cin >> i >> j;

			int weight = 0;
			cout << "Please input weight value: " << endl;
			cin >> weight;
			g->edge[i][j] = weight;
			//g->edge[j][i] = weight;//如果是无向图要加上；
		}

		return g;
	}
	else
	{
		cout << "Memory allocate is error! " << endl;
		system("pause");
		exit(0);
	}
}

void BFS(PAMGraph g, int i)
{
	PSeqQueue q = InitSeqQueue();

	cout << g->vertex[i] << endl;
	visited[i] = true;
	InSeqQueue(q, i);

	while (!EmptySeqQueue(q))
	{
		OutSeqQueue(q, &i);

		for (int j = 0; j < g->vertexNum; j++)
		{
			if (g->edge[i][j] == 1 && !visited[j])
			{
				cout << g->vertex[j] << endl;
				visited[j] = true;
				InSeqQueue(q, j);
			}
		}
	}
}

void BFSTraversal(PAMGraph g)
{
	for (int i = 0; i < g->vertexNum; i++)
	{
		visited[i] = false;
	}

	for (int i = 0; i < g->vertexNum; i++)
	{
		if (!visited[i])
		{
			BFS(g, i);
		}
	}
}

void MiniSpanTreePrim(PAMGraph g, int u)
{
	//定义迭代变量；
	int i = 0; 
	int j = 0;
	int k = 0;

	//动态生成辅助数组；
	AuxArray * array = new AuxArray[g->vertexNum];

	//将辅助数组从u开始初始化；
	for (i = 0; i < g->vertexNum; i++)
	{
		array[i].adjvertex = u;
		array[i].lowcost = g->edge[u][i];
	}

	for (i = 0; i < g->vertexNum - 1; i++)
	{
		//设置象征意义的无穷大；
		int v = INFINITY;
		//查找最小的边；
		for (j = 0; j < g->vertexNum; j++)
		{
			//当前元素不是U集且小于v;
			if ((array[j].lowcost != 0) && (array[j].lowcost < v))
			{
				v = array[j].lowcost;
				k = j;
			}
		}
		//将最小的边置0；即进入U集；
		array[k].lowcost = 0;

		//更新辅助数组；
		for (j = 0; j < g->vertexNum; j++)
		{
			if (g->edge[k][j] < array[j].lowcost)
			{
				array[j].adjvertex = k;
				array[j].lowcost = g->edge[k][j];
			}
		}
	}

	//总权值；
	int w = 0;
	//统计信息；
	for (i = 0; i < g->vertexNum; i++)
	{
		//跳过开始的元素；
		if (i != u)
		{
			cout << i << "->" << array[i].adjvertex << ", " << g->edge[i][array[i].adjvertex] << endl;
			w += g->edge[i][array[i].adjvertex];
		}
	}

	cout << "Total weight = " << w << endl;
}

void ShortestPathDij(PAMGraph g, int u, int * D, int * P)
{
	//定义迭代变量；
	int i = 0;
	int j = 0;
	int k = 0;
	int min = 0;

	//定义标志数组；
	int * flag = (int *)malloc(g->vertexNum * sizeof(int));

	//初始化D， P， flag数组；
	for (i = 0; i < g->vertexNum; i++)
	{
		flag[i] = false;
		D[i] = g->edge[u][i];
		P[i] = -1;
		if (D[i] < INFINITY)
		{
			P[i] = u;
		}
	}
	flag[u] = true;
	P[u] = -1;

	//主for循环；
	for (i = 0; i < g->vertexNum; i++)
	{
		//查找最短路径；
		k = -1;
		min = INFINITY;
		for (j = 0; j < g->vertexNum; j++)
		{
			if ((!flag[j]) && (D[j] < min))
			{
				k = j;
				min = D[j];
			}
		}
		if (k == -1)
		{
			break;
		}
		flag[k] = true;

		//更新D 和 P数组；
		for (j = 0; j < g->vertexNum; j++)
		{
			if ((!flag[j]) && (min + g->edge[k][j] < D[j]))
			{
				D[j] = min + g->edge[k][j];
				P[j] = k;
			}
		}
	}
}

void ShortestPathFloyd(PAMGraph g, int ** D, int ** P)
{
	int i = 0;
	int j = 0;
	int k = 0;

	for (i = 0; i < g->vertexNum; i++)
	{
		for (j = 0; j < g->vertexNum; j++)
		{
			D[i][j] = g->edge[i][j];
			//这个if-else是记录路径的，目前我还没有搞清楚；
			if (D[i][j] < INFINITY)
			{
				P[i][j] = i;
			}
			else
			{
				P[i][j] = -1;
			}
		}
	}

	for (k = 0; k < g->vertexNum; k++)
	{
		for (i = 0; i < g->vertexNum; i++)
		{
			for (j = 0; j < g->vertexNum; j++)
			{
				if (D[i][k] + D[k][j] < D[i][j])
				{
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k;
				}
			}
		}
	}

	return;
}

//void Show(int i, int j, int ** D, int ** P)
//{
//	cout << D[i][j] << " " << j << "<-";
//	while (P[i][j] != -1)
//	{
//		cout << P[i][j] << "<-";
//		j = P[i][j];
//	}
//
//	return;
//}

Main函数；

# include "AMGraph.h"

int main(int argc, char ** argv)
{
	AMGraph g;
	g.vertexNum = 6;
	g.edgeNum = 8;

	for (int i = 0; i < g.vertexNum; i++)
	{
		for (int j = 0; j < g.vertexNum; j++)
		{
			if (i == j)
			{
				g.edge[i][j] = 0;
			}
			else
			{
				g.edge[i][j] = INFINITY;
			}
		}
	}

	g.edge[0][5] = 100;
	g.edge[0][4] = 30;
	g.edge[0][2] = 10;
	g.edge[1][2] = 5;
	g.edge[2][3] = 50;
	g.edge[3][5] = 10;
	g.edge[4][3] = 20;
	g.edge[4][5] = 60;

	//cout << "----------------------------" << endl;
	//BFSTraversal(g);

	//cout << "----------------------------" << endl;
	//MiniSpanTreePrim(g, 3);

	//int * D = new int[g.vertexNum];
	//int * P = new int[g.vertexNum];
	//ShortestPathDij(&g, 0, D, P);

	//for (int i = 0; i < g.vertexNum; i++)
	//{
	//	cout << D[i] << endl;
	//}

	//for (int i = 0; i < g.vertexNum; i++)
	//{
	//	if (P[i] == -1)
	//	{
	//		continue;
	//	}
	//	
	//	cout << i << "<-";
	//	int j = i;
	//	while (P[j] != -1)
	//	{
	//		cout << P[j] << "<-";
	//		j = P[j];
	//	}
	//	
	//	cout << ", " << D[i] << endl;
	//}

	AMGraph gg;
	gg.vertexNum = 3;
	gg.edgeNum = 5;

	for (int i = 0; i < gg.vertexNum; i++)
	{
		for (int j = 0; j < gg.vertexNum; j++)
		{
			//gg.edge[i][j] = INFINITY;
			if (i == j)
			{
				gg.edge[i][j] = 0;
			}
			else
			{
				gg.edge[i][j] = INFINITY;
			}
		}
	}

	gg.edge[0][1] = 4;
	gg.edge[0][2] = 11;
	gg.edge[2][0] = 3;
	gg.edge[1][0] = 6;
	gg.edge[1][2] = 2;

	int ** DD = (int **)malloc(gg.vertexNum * sizeof(int *));
	for (int i = 0; i < gg.vertexNum; i++)
	{
		DD[i] = (int *)malloc(gg.vertexNum * sizeof(int));
	}

	int ** PP = new int *[gg.vertexNum];
	for (int i = 0; i < gg.vertexNum; i++)
	{
		PP[i] = new int[gg.vertexNum];
	}

	ShortestPathFloyd(&gg, DD, PP);

	cout << endl << "----------------------------------" << endl;
	for (int i = 0; i < gg.vertexNum; i++)
	{
		for (int j = 0; j < gg.vertexNum; j++)
		{
			cout << DD[i][j] << endl;
		}
	}

	cout << endl << "----------------------------------" << endl;
	Show(0, 1, DD, PP);
	cout << "--------" << endl;
	Show(2, 0, DD, PP);
	cout << "--------" << endl;
	Show(0, 2, DD, PP);

	system("pause");
	return 0;
}
动态规划 数据结构 floyd算法
上一篇: floyd算法_常见算法总结
下一篇: 最短路径（图）

继续阅读