菏泽网站建设电话咨询,昆明app制作公司在哪里,自己做网站用什么app,微信小程序模板使用Floyd算法 Floyd算法 Dijkstra算法是用于解决单源最短路径问题的#xff0c;Floyd算法则是解决点对之间最短路径问题的。Floyd算法的设计策略是动态规划#xff0c;而Dijkstra採取的是贪心策略。当然#xff0c;贪心算法就是动态规划的特例。 算法思想 点对之间的最短路径仅… Floyd算法 Floyd算法 Dijkstra算法是用于解决单源最短路径问题的Floyd算法则是解决点对之间最短路径问题的。Floyd算法的设计策略是动态规划而Dijkstra採取的是贪心策略。当然贪心算法就是动态规划的特例。 算法思想 点对之间的最短路径仅仅会有两种情况 两点之间有边相连。weight(Vi,Vj)即是最小的。通过还有一点中介点两点相连使weight(Vi,Vv)weight(Vv,Vj)最小。Min_Distance(Vi,Vj)min{weight(Vi,Vj),weight(Vi,Vv)weight(Vv,Vj)}。正是基于这样的背后的逻辑。再加上动态规划的思想构成了Floyd算法。故当Vv取全然部顶点后Distance(Vi,Vj)就可以达到最小。Floyd算法的起点就是图的邻接矩阵。 题外话代码本身不重要。算法思想才是精髓。思想极难得到而有了思想稍加经验就可以写出代码。向思想的开创者致敬。 思想非常难。代码却比較简单。直接上代码 代码 类定义 #includeiostream
#includeiomanip
#includestack
using namespace std;
#define MAXWEIGHT 100
#undef INFINITY
#define INFINITY 1000
class Graph
{
private://顶点数 int numV;//边数 int numE;//邻接矩阵 int **matrix;
public:Graph(int numV);//建图 void createGraph(int numE);//析构方法 ~Graph();//Floyd算法void Floyd();//打印邻接矩阵 void printAdjacentMatrix();//检查输入 bool check(int, int, int);
};类实现 //构造函数指定顶点数目
Graph::Graph(int numV)
{//对输入的顶点数进行检測while (numV 0){cout 顶点数有误又一次输入 ; cin numV; } this-numV numV; //构建邻接矩阵。并初始化 matrix new int*[numV]; int i, j; for (i 0; i numV; i) matrix[i] new int[numV]; for (i 0; i numV; i) for (j 0; j numV; j) { if (i j) matrix[i][i] 0; else matrix[i][j] INFINITY; } } void Graph::createGraph(int numE) { /* 对输入的边数做检測 一个numV个顶点的有向图最多有numV*(numV - 1)条边 */ while (numE 0 || numE numV*(numV - 1)) { cout 边数有问题又一次输入 ; cin numE; } this-numE numE; int tail, head, weight, i; i 0; cout 输入每条边的起点(弧尾)、终点(弧头)和权值 endl; while (i numE) { cin tail head weight; while (!check(tail, head, weight)) { cout 输入的边不对请又一次输入 endl; cin tail head weight; } matrix[tail][head] weight; i; } } Graph::~Graph() { int i; for (i 0; i numV; i) delete[] matrix[i]; delete[]matrix; } /* 弗洛伊德算法 求各顶点对之间的最短距离 及其路径 */ void Graph::Floyd() { //为了不改动邻接矩阵多用一个二维数组 int **Distance new int*[numV]; int i, j; for (i 0; i numV; i) Distance[i] new int[numV]; //初始化 for (i 0; i numV; i) for (j 0; j numV; j) Distance[i][j] matrix[i][j]; //prev数组 int **prev new int*[numV]; for (i 0; i numV; i) prev[i] new int[numV]; //初始化prev for (i 0; i numV; i) for (j 0; j numV; j) { if (matrix[i][j] INFINITY) prev[i][j] -1; else prev[i][j] i; } int d, v; for (v 0; v numV; v) for (i 0; i numV; i) for (j 0; j numV; j) { d Distance[i][v] Distance[v][j]; if (d Distance[i][j]) { Distance[i][j] d; prev[i][j] v; } } //打印Distance和prev数组 cout Distance... endl; for (i 0; i numV; i) { for (j 0; j numV; j) cout setw(3) Distance[i][j]; cout endl; } cout endl prev... endl; for (i 0; i numV; i) { for (j 0; j numV; j) cout setw(3) prev[i][j]; cout endl; } cout endl; //打印顶点对最短路径 stackint s; for (i 0; i numV; i) { for (j 0; j numV; j) { if (Distance[i][j] 0); else if (Distance[i][j] INFINITY) cout 顶点 i 到顶点 j 无路径 endl; else { s.push(j); v j; do{ v prev[i][v]; s.push(v); } while (v ! i); //打印路径 cout 顶点 i 到顶点 j 的最短路径长度是 Distance[i][j] 其路径序列是...; while (!s.empty()) { cout setw(3) s.top(); s.pop(); } cout endl; } } cout endl; } //释放空间 for (i 0; i numV; i) { delete[] Distance[i]; delete[] prev[i]; } delete[]Distance; delete[]prev; } //打印邻接矩阵 void Graph::printAdjacentMatrix() { int i, j; cout.setf(ios::left); cout setw(7) ; for (i 0; i numV; i) cout setw(7) i; cout endl; for (i 0; i numV; i) { cout setw(7) i; for (j 0; j numV; j) cout setw(7) matrix[i][j]; cout endl; } } bool Graph::check(int tail, int head, int weight) { if (tail 0 || tail numV || head 0 || head numV || weight 0 || weight MAXWEIGHT) return false; return true; }主函数 int main()
{cout ******Floyd***by David*** endl;int numV, numE;cout 建图... endl;cout 输入顶点数 ;cin numV;Graph graph(numV);cout 输入边数 ;cin numE;graph.createGraph(numE);cout endl Floyd... endl;graph.Floyd();system(pause);return 0;
}执行 小结 Floyd算法代码看似非常长事实上并不难。代码中非常多都是用于准备工作和输出。关键代码就是三层for循环。 完整代码下载Floyd算法 转载请注明出处本文地址http://blog.csdn.net/zhangxiangdavaid/article/details/38366923 若有所帮助顶一个哦。 专栏文件夹 数据结构与算法文件夹c指针 版权声明本文博主原创文章。转载转载请注明出处。 转载于:https://www.cnblogs.com/gcczhongduan/p/4850988.html
