20180728最短路径最小生成树

1、欧拉图和哈密尔顿图，柯尼斯堡七桥问题，1，欧拉图，1)定义：欧拉路径通过图的每一边一次，并且只通过一个顶点。欧拉路径在图中穿过每条边一次并且只穿过一次，并且穿过每个顶点的环。欧拉图带有欧拉路径。定理1:欧拉路径的条件：图是连通的，并且有0或2个奇点。如果有两个奇点，欧拉路径必须从一个奇点开始，以另一个奇点结束。定理2:欧拉路径的条件：图是连通的，没有奇点。下列数字能一笔画出吗？练习：3)寻找欧拉路径的算法，void find _ circuit(inti ) intj；对于(j=1；j=n。j)如果(gij=1)/从与其相连的任何点开始 gjI=gIj=0；find _ circuit(j)；

2、电路电路=I；/记录路径如果您正在寻找欧拉路径，请执行find _ circuit在任何一点上；如果搜索到欧拉路径，则查找电路；对奇点执行；该算法的时间复杂度为0(m n)。1)定义：哈密尔顿路径是在图中穿过每个顶点一次且仅一次的路径。汉密尔顿循环通过该循环一次，并且对于图中的每个顶点仅通过一次。哈密尔顿图带有哈密尔顿环的图。(2)判断：不幸的是，还没有找到区分哈密顿回路和路径的充分必要条件。(3)哈密尔顿环的算法通常通过搜索来求解。哈密尔顿图、最短路径最小生成树、李云军和最短路径问题是网络理论解决的典型问题之一，可用于解决管道铺设、线路安装、工厂布局和设备更新等实际问题。基本内容是：如果网络

3、中的每条边都有一个值(长度、成本、时间等)。)，寻找两个节点(通常是源节点和汇节点)之间的总权重和最小路径是最短路径问题。一般来说，有两种类型的最短路径问题：一种是寻找从一个顶点(源点)到其他顶点(目的点)的最短路径(迪克斯特拉算法、贝尔曼-福特算法、SPFA算法)；另一种是寻找图中每对顶点之间的最短路径(弗洛伊德算法：弗洛伊德)。Floyd算法：寻找任意一对顶点之间的最短路径。原理：如果我们已经知道只有编号为k-1的点被允许作为图中任意两点之间的最短路径，我们能推断出只有编号为k的点被允许作为任意两点之间的最短路径吗？if(dIkdkjnmpq；对于(inti=1；iijkdIj=k；djI

4、=k；，voulfloyed() for(intk=1；k=n；k)对于(inti=1；i=n。I)对于(intj=1；j=n。j)如果(dIkdkjn；对于(I=1；IXIyI；对于(I=1；IC；如果(c=1)fij=dist(i，j)；否则 if(I=j)fIj=0；elsefIj=max int；，对于(k=1；KFIkfkj)fIj=fIkfkj；memset(m，0，sizeof(m)；对于(I=1；i=n。I)对于(j=1；j=n。如果(fIjmImjtemp)minx=mImjtemp； r=0；对于(I=1；minx=mI；printf(“% . 6 lf”，minx)；返回

5、0；，Dijkstra算法(从一个顶点到其他顶点的最短路径，单源最短路径)算法描述：设置起点为s，disv代表从s到v的最短路径，pathv是v的前驱节点，用于输出路径。a)初始化：disv=(vs)；diss=0；路径s=0；(I=1；i=n。一)1 .在一个没有被访问过的点上找到一个顶点，这样disu是最小的。2.u被标记为确定的最短路径3。对于顶点Vif(disUwUvn连接到U的每个未确定最短路径的起点；intx，y，w；对于(inti=1；ixywaxy=w；ayx=w；，void Dijkstra(ints) for(inti=1；i=n。I) dI=INF；fI=false； d

6、s=0；对于(inti=1；i=n。I) intmind=INF；intk/用于记录(intj=1；j=n。/如果(！fj)，voiddfs(inti)if(i！=start)dfs(路径I)；coutn对于(I=1；iaI1aI2；cinmmemset(f，0 x7f，size of(f)；/将F数组初始化为(I=1；ixyfyx=fxy=sqrt(幂(双(ax1-ay1)，2)幂(双(ax2-ay2)，2)；/power(x，y)表示x，y，其中x，y必须是双精度类型，并使用cmath库 cinse对于(k=1；k=n；K )/floyed最短路径算法(I=1；i=n。I)对于(j=1；j

7、=n。j)如果(I！=j)，例5:最低费用问题描述在n个人中，一些人的银行账户可以相互转账。这些人之间的转账手续费各不相同。如果在这些人之间转账时，手续费从转账金额中扣除了多少百分比，那么在转账后，甲至少需要多少才能让乙收到100元？输入格式在第一行输入两个正整数n、m，分别代表可以相互转账的总人数和人数的对数。在以下m行中的每一行中输入三个正整数x、y、z，表示x号和y号之间的转账将扣除z%手续费(z100)。在最后一行中输入两个正整数A、B。数据保证A和B之间可以进行直接或间接的转移输出格式输出A使B至少达到100元所需的总成本。精确到小数点后8位。输入样本332123213313输出样本

8、103.07153164数据标度1=nnm；对于(I=1；ixy，void Dijkstra(intx) for(I=1；IMAX n) k=j；maxn=disj； fk=1；如果(k=y)断开；对于(j=1；jdisj)disj=disk* akj；，int main() init()；Dijkstra(x)；printf(“% 0.8 lf”，100/disy)；返回0；Bellman-Ford算法简称为Ford算法，也用于计算从一点到所有其他点的最短路径，也是单源最短路径算法。可以处理负边缘权重的情况，但不能处理负权重循环的情况(将在下面详细描述)。算法的时间复杂度：0(NE)，n是顶点数，e是边数。算法实现：以s为起点，disv是从s到v的最短距离，prev是v的前身，Wj是边j的长度，j连接u和v，初始化：diss=0，disv=(vs)，pres=0或(I=1；I=n-1；(j=1；j=E；/注意枚举所有的边，而不是点。if(disuwjn；对于(I=1；igIj；memset(minn，0 x7f，siz