Floyd

Floyd算法

• 算法思想

  • 一次解决全图

    using AMGraph = struct {
    	int arcnum{ 0 };
    	int vexnum{ 0 };
    	VerTexType vertices[MVNum];
    	ArcType arcs[MVNum][MVNum];
    };

  • 插点的循环

    for (k = 0; k < G.vexnum; k++)	// 第一个
    		for(v=0;v<G.vexnum;v++)
    			for(w=0;w<G.vexnum;w++)
    			{
    				if (C[v][w] >C[v][k] +C[k][w])
    				{
    					C[v][w] = C[v][k] +C[k][w];
    					P[v][w] = P[v][k];		//相当于就是在里面加点 最后一个我们读取矩阵
    				}
    			}

• 代码细节

  /*****************************************************************//**
   * \file   Floyd.cpp
   * \brief  For Ms.Winter
   *  3/27/2023
   * \author 86158
   * \date   March 2023
   *********************************************************************/
  // Floyd
  //关键思想就是不断的插入点来分析 
  #define _CRT_SECURE_NO_WARNINGS
  #include<iostream>
  #include<cstdio>
  #include<cstdlib>
  using namespace std;
  //
  #define OK	1
  #define BAD	0
  #define MVNum	50
  
  using Path = int[MVNum][MVNum];		
  using ShortPathTable = int[MVNum][MVNum];
  
  // 最精妙的思想 一次求完所有的点 所以这是一个n^3复杂度
  
  // 同样使用邻接矩阵
  using VerTexType = char;
  using ArcType = int;
  using AMGraph = struct {
  	int arcnum{ 0 };
  	int vexnum{ 0 };
  	VerTexType vertices[MVNum];
  	ArcType arcs[MVNum][MVNum];
  };
  
  void Floyd(const AMGraph& G,Path P,ShortPathTable C)
  {
  	int v, w, k;
  	for(v=0;v<G.vexnum;v++)
  		for (int w = 0; w < G.vexnum; w++)
  		{
  			C[v][w] = G.arcs[v][w];
  			P[v][w] = w;	// 注意这个初始化
  		}
  	// 非常巧妙的循环也是关键
  	for (k = 0; k < G.vexnum; k++)	// 第一个
  		for(v=0;v<G.vexnum;v++)
  			for(w=0;w<G.vexnum;w++)
  			{
  				if (C[v][w] >C[v][k] +C[k][w])
  				{
  					C[v][w] = C[v][k] +C[k][w];
  					P[v][w] = P[v][k];		//相当于就是在里面加点 最后一个我们读取矩阵
  				}
  			}
  }
  // 注意我们的这个路径矩阵 与迪杰斯特拉一样 然后是列来读取
  // 数值 横着读取
  
  void Dispath(const AMGraph& G, Path P, ShortPathTable C)
  {
  	int k = 0;
  	cout << "各点的最短路径如下\n";
  	for (int v = 0; v < G.vexnum-1; v++)
  		for (int w = v + 1; w < G.vexnum; w++)		// 只读取一般矩阵 也很好哦
  		{
  			cout << "v" << v << "-v" << w << " weight: " << C[v][w];
  			k = P[v][w];
  			cout << " Path: " << v;
  			while (k != w)
  			{
  				k = P[k][w];
  				cout << "->" << k;
  			}
  			cout << "->" << w << endl;
  		}
  }

总结

最后其实就是这种插点的思想