3.1GN算法的数学概念大口鲶鱼苗项目投资可行性报告
GN算法的基本思路是不断的从网络中移除介数最大的边。
假设一个图的节点数为n,边数为m,利用广度优先搜索就可以得到一个节点与其他节点的所有最短路劲，所有这些最短路径构成最短路径树。根据源节点与其他节点间最短路径的条数，分两种情况进行讨论。
情况一：每个源节点与其他节点之间只存在一条最短路径
步骤1:找到这棵树的叶结点，即那些不被任何其他节点间的最短路径经过的节点，每一条与叶结点相连的边赋值为1。
步骤2:从离树的源节点最远的一条边开始逐步上移，依次为每条边赋值,其值为紧接在该边下的所有邻边的值的和再加1，重复步骤2直到这棵树的所有的边。
步骤3:对所有可能的源节点重复该过程，然后把这些边每次的权值相加，最终结果即为所有节点对之间最短路径的边介数。
情况1
情况二：节点对之间存在若干条等长度最短路径。
此时的结构并非是一棵树了（如图），在这种情况下，为了保证算法的正确性，需要添加其他步骤：
（1）计算源节点到其他各节点的最短路径的条数
（2）利用这些条数为各条路径增加一个相应的权值 （若i、j之间存在n条最短路径，则每条路径的权值都为1/n）。
对所有源节点重复上述过程，将每次的权值相加，就可以得到所有的边的总介数。
情况2
3.2GN算法的详细设计
（1）计算从源节点s到其他各节点的最短路径的条数（wi）
①定义源节点s的距离，权值
②对每个与源节点毗邻的节点i，定义其距离为，权值
③对于与这个节点i任意相连的节点j，分下列三种情况讨论：
（a）如果该节点并没有指定距离值，则指定其距离为dj=di+1权值为
（b）如果该节点已经指定了距离值，且dj=di+1，该节点的权值变为
（c）如果该节点已经指定了距离值，且dj<di+1，直接转向步骤④。
④重复执行第③步，直到不存在其本身指定了距离值而相邻节点没有指定距离值的节点为止。
注：di表示从源节点到节点i的距离,wi表示从源节点到节点i的最短路径的条数。
（2）为各条路径增加一个相应的权值
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页