地理信息系统课程GIS网络分析

1、网络分析模型网络分析模型1 1 网络分析基础网络分析基础2 2 最短路径分析最短路径分析3 3 最佳路径分析最佳路径分析4 4 资源分配资源分配将一批货物从甲地运到乙地，可以经过多条路线，如何求取将一批货物从甲地运到乙地，可以经过多条路线，如何求取运输费用最低的路线运输费用最低的路线最佳路径最佳路径 当地下煤气管道改装时，若关闭某个阀门，需要确定受影当地下煤气管道改装时，若关闭某个阀门，需要确定受影响的用户响的用户连通问题连通问题某城市拟建立一消防站，如何确定某城市拟建立一消防站，如何确定1010分钟之内能达到的所有分钟之内能达到的所有街道街道资源分配资源分配常乐村常乐村1515号在那个地方号

2、在那个地方地址匹配地址匹配 问题引入：问题引入：什么是网络分析什么是网络分析? ? 在在GISGIS中，网络分析是指依据网络拓扑关系（结点与弧中，网络分析是指依据网络拓扑关系（结点与弧段拓扑、弧段的连通性），通过考察网络元素的空间及属性段拓扑、弧段的连通性），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方数据，以数学理论模型为基础，对网络的性能特征进行多方面研究的一种分析计算。面研究的一种分析计算。 问题引入：问题引入：1 1 网络分析基础网络分析基础 网络网络：是由点、线构成的系统，通常用来描述某种资源：是由点、线构成的系统，通常用来描述某种资源或物质在空间

3、中的运动。可表示为由网络结点集或物质在空间中的运动。可表示为由网络结点集V V、网络边集、网络边集E E和事件点集和事件点集P P组成的集合，即有组成的集合，即有D = VD = V，E E，PP 网络分析网络分析：是对地理网络和城市基础设施网络等网状事：是对地理网络和城市基础设施网络等网状事物以及它们的相互关系和内在联系进行地理分析和模型化。物以及它们的相互关系和内在联系进行地理分析和模型化。 网络分析的基本研究对象网络分析的基本研究对象：线状目标和点状目标。：线状目标和点状目标。 网络分析的主要研究内容网络分析的主要研究内容：最短路径分析、资源分配、：最短路径分析、资源分配、连通分析等。连

4、通分析等。由一系列相互连通的点和线组成，用来描述地理要素（资由一系列相互连通的点和线组成，用来描述地理要素（资源）的流动情况。源）的流动情况。1 1 网络分析基础网络分析基础 网络基本元素网络基本元素包括网络中心、边、结点、站、拐角包括网络中心、边、结点、站、拐角和障碍等，如下图。和障碍等，如下图。 1 1 网络分析基础网络分析基础 1 1、资源资源：是网络中传输的物质、能量、信息等。资源通过在：是网络中传输的物质、能量、信息等。资源通过在网络中的流动实现传输和分配。网络中的流动实现传输和分配。 资源属性与网络通行规则联合作用影响资源在网络中的流动资源属性与网络通行规则联合作用影响资源在网络中

5、的流动情况。情况。 2 2、链链：图或网络中的线状要素，表现的是网络中的地理实体：图或网络中的线状要素，表现的是网络中的地理实体和现象，通常用中心线代表地理实体和现象本身。和现象，通常用中心线代表地理实体和现象本身。 链有链有图形信息图形信息和和属性信息属性信息。属性信息包括阻碍强度、资源需。属性信息包括阻碍强度、资源需求量、资源流动的约束条件。求量、资源流动的约束条件。 2) 2) 道路是一双行道，且正向阻强为道路是一双行道，且正向阻强为4040km/skm/s，负向阻强为负向阻强为3535km/skm/s，具体表达为具体表达为链弧号链弧号起结点起结点终结点终结点正 方 向 阻 强正 方 向

6、 阻 强（km/skm/s）反 方 向 阻 强反 方 向 阻 强（km/skm/s）p1p7p1p71 17 740403535 3 3）道路是一单行道，且阻强为）道路是一单行道，且阻强为2020km/skm/s，具体表达为：具体表达为：链弧号链弧号起结点起结点终结点终结点正 方 向 阻 强正 方 向 阻 强（km/skm/s）反 方 向 阻 强反 方 向 阻 强（km/skm/s）P6p8P6p86 68 82020-1(-1(表不通表不通) ) 3 3、结点结点：网络链的两个端点：网络链的两个端点 4 4、站点站点：网络中装载或卸下资源的结点位置。：网络中装载或卸下资源的结点位置。 站的属

7、性主要有两种：资源需求量和阻碍强度。站的属性主要有两种：资源需求量和阻碍强度。 5 5、中心中心：网络中具有一定的容量，能够从链上获取资源的结点所在：网络中具有一定的容量，能够从链上获取资源的结点所在地。地。 中心的属性有两种：一是中心的属性有两种：一是中心的资源容量中心的资源容量，一是，一是中心的阻碍强度中心的阻碍强度。 6 6、障碍障碍：对资源传输起阻断作用的结点或链，它阻碍了资源在与其：对资源传输起阻断作用的结点或链，它阻碍了资源在与其相连的链间的流动，代表了网络中元素的不可通行状态。（相连的链间的流动，代表了网络中元素的不可通行状态。（障碍持续障碍持续） 7 7、拐角拐角：网络结点处，

8、所有资源流动的可能的转向。其属性：网络结点处，所有资源流动的可能的转向。其属性主要是拐角的阻碍强度。主要是拐角的阻碍强度。 8 8、权值权值：用于存储通过一条链或结点时所需要的成本。：用于存储通过一条链或结点时所需要的成本。2 2 最短路径分析最短路径分析 路径分析路径分析：是在指定网络的结点间找出最佳路径。是在指定网络的结点间找出最佳路径。 最短路径最短路径：在网络两节点之间找到一条抗阻最小的：在网络两节点之间找到一条抗阻最小的路径。路径。 路径分析的关键路径分析的关键：对路径的求解，即如何求出满足条件对路径的求解，即如何求出满足条件的最优路径。的最优路径。 DijkstraDijkstra

9、算法算法 Dijkstra Dijkstra算法是最经典的按路径长度递增的次序产生最短路径算法是最经典的按路径长度递增的次序产生最短路径的方法。的方法。 DijkstraDijkstra算法的基本思想算法的基本思想：标记源点到已得到点的最短路径，：标记源点到已得到点的最短路径，再寻找到下一个点的最短路径（由近及远寻找起点到其他节点的最再寻找到下一个点的最短路径（由近及远寻找起点到其他节点的最佳路径，直至到达目标节点）。适用于所有弧的佳路径，直至到达目标节点）。适用于所有弧的权为非负权为非负的最短路的最短路径算法。径算法。 DijkstraDijkstra算法的具体步骤算法的具体步骤： （1 1

10、）初始化：设置源）初始化：设置源s s点：点：d ds s=0,p=0,ps s= =空集空集; ;其他点：其他点：d ds s=,p=,ps s=?;=?;将起源点将起源点s s标号，记标号，记k=sk=s，其他点尚未处理；，其他点尚未处理； （2 2）距离计算。计算从所有标记的点）距离计算。计算从所有标记的点k k到其他直接连接的未标记到其他直接连接的未标记的点的点j j的距离的距离l lijij，并令，并令 d dj j = mind = mindj j，d dk k + l+ lkjkj （3 3）选取下一点。从上述结点集中，选取）选取下一点。从上述结点集中，选取d dj j最小所对应

11、的点为最短最小所对应的点为最短路径中的下一连接点路径中的下一连接点i i，并作标记。，并作标记。 （4 4）找到点）找到点i i的前一点。从已标记的点中找到连接到点的前一点。从已标记的点中找到连接到点i i的前的前一点一点j j* *, ,并令并令i=ji=j* *作为前一点。作为前一点。 （5 5）标记点）标记点i i。如果所有点已标记，则算法完全退出，否则，。如果所有点已标记，则算法完全退出，否则，记记k=ik=i，转到（，转到（2 2）再继续，直到所有点都已标记。）再继续，直到所有点都已标记。 v 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段

12、之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）3 3 资源分配资源分配 一、基本概念：一、基本概念： 资源分配资源分配：在网络中根据应用需求将资源分配到所需的地点。在网络中根据应用需求将资源分配到所需的地点。 资源分配的研究问题资源分配的研究问题包括：包括： （1 1）需求点和供应点都确定的情况下，现在资源的分配，如物资）需求点和供应点都确定的情况下，现在资源的分配，如物资配送；配送； （2 2）新增供应点，如新的变电所选址；）新增供应点，如新的变电所选址； （3 3）新增需求点，如新建居民地。）新增需求点，如新建居民地。 资源分配的核心资源分配的核

13、心：资源的定位及分配。资源的定位及分配。 资源的定位资源的定位：指已知需求，确定在哪里布设最合适的供应点，即：指已知需求，确定在哪里布设最合适的供应点，即寻找最佳的供应点。寻找最佳的供应点。 资源的分配资源的分配：就是确定需求源分别受哪个供应点服务。：就是确定需求源分别受哪个供应点服务。3 3资源分配资源分配 资源分配的数学模型：资源分配的数学模型： 设有设有n n个需求点个需求点P Pi i（x xi i,y,yi i），），b bi i是每个需求点的需求量是每个需求点的需求量（i=1,2,i=1,2,n,n）, , m m个供应点个供应点Q Q j j（u uj j,v,vj j） （j=

14、1,2,j=1,2,m,m） 。t tijij和和d dijij分别是供应点分别是供应点Q Qj j对需求对需求点点P Pi i提供的供应量和两点间的距离。提供的供应量和两点间的距离。 若所有的需求点都受到供应点的服务，则若所有的需求点都受到供应点的服务，则 若每个需求点都分配给与之最近的一个供应点，则若每个需求点都分配给与之最近的一个供应点，则 需求点需求点P Pi i的需求是否由供应点的需求是否由供应点Q Q j j供给可用矩阵（供给可用矩阵（X Xijij）表示，且）表示，且mjiijnibt1,2, 1,其他情况当,0;,2, 1,jkmkddbtikijiij其他情况供给受, 0,

15、1jiijQPX3 3 资源分配资源分配 二、资源分配目标方程资源分配目标方程 若资源分配要求供应点与需求点之间总的加权距离为最小，若资源分配要求供应点与需求点之间总的加权距离为最小，则相应的目标方程是则相应的目标方程是 若要求距离最小时，目标方程是若要求距离最小时，目标方程是 若要求所有的需求点在一给定的服务半径若要求所有的需求点在一给定的服务半径s s内，则目标方程内，则目标方程是是 其中其中 nimjijid11minsdsddcijijijiij,nimjijd11min nimjijc11min4 4、连通性分析、连通性分析-最小生成树最小生成树（1 1）概念）概念连通图：在一个图中

16、，任意两个节点之间都连通图：在一个图中，任意两个节点之间都存在一条路。存在一条路。树：若一个连通图中不存在任何回路，则称树：若一个连通图中不存在任何回路，则称为树。为树。生成树的权数：生成树中各边的权数之和。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。最小生成树：图的极小连通子图。（2 2）应用：通信线路、快递）应用：通信线路、快递56树中的边数比节点数少树中的边数比节点数少1 1树中两节点之间最多有一条边树中两节点之间最多有一条边树中任意去掉一条边，就变成不连通的图树中任意去掉一条边，就变成不连通的图树中添加一条边就会构成回路树中添加一条边就会构成回路一般来说，一个图

17、生成的树可能不止一个一般来说，一个图生成的树可能不止一个树的性质树的性质(4)(4)算法（算法（KruskalKruskal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并取权数最小的一）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。有的边，构成回路，则舍去该边，否则选中生成树。3 3）重复）重复2 2），直到有），直到有M-1M-1条边被选进生成树中，这条边被选进生成树中，这M-1M-1条边就构成条边就构成最小生成树最小生成树具体步骤具体步骤(4)(4)算法（算法（KruskalKruskal，克罗斯克尔算法，也叫克罗斯克尔算法，也叫“避圈避圈”法）法）1 1）先把图中的各边按权数从小到大重新排列，并取权数最小的一）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。条边为最小生成树中的边。2 2）在剩下的边中，按顺序取下一条边