图论的基本算法.pptVIP

Car的旅行路线又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。那么Car应如何安排到城市B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。约束条件输入第一行为一个正整数n(0≤n≤10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。s（0＜S≤100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1≤A，B≤S）。 接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1-)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。输出 共有n行，每行一个数据对应测试数据。分析计算两点间的欧氏距离计算每个机场的坐标序列使用Dijkstra算法计算最小费用SSSP：权非负的情形求1到所有点的距离d[1]=0d[2]=3,d[4]=4d[2]=3.为什么？每次固定d的最小值标号设定！怎样取最小值？堆！名称：dijkstra和Prim算法很类似Prim:边最小值dijkstra:d最小值中间结果：最短路树！时间复杂度O((m+n)logm)一个例子给出一个带权无向图G边权为1…1000的整数对于v0到v1的任意一条简单路p定义s(p)为p上所有边权的最大公约数考虑v0到v1的所有路p1,p2,…求所有s(p1),s(p2),…的最小公倍数模型？最短路？路径长度定义不再是权和，而是…dijkstra算法还能用吗？SSSP：权任意的情形最短路有可能不存在！什么时候不存在？有负圈！标号设定?标号修正仍然有标号d[i]=k但是标号d[i]无法固定，只能不断更新新算法如有最短路，则每个顶点最多经过一次即：这条路不超过n-1条边迭代！依次考虑1,2,3…n-1条边的情形SSSP：bellman-ford算法依次考虑边长度不超过1,2…n-1的路考虑长度不超过1,2,3…k-1的路后，标号为d[]长度为k的路可以由不超过1,2,…k-1的路增加一条边得到：fork:=1ton-1dofor每条边(u,v)doif(d[u]∞)and(d[v]d[u]+w(u,v))thend[v]:=d[u]+w(u,v)核心：标号修正过程（松弛操作）时间复杂度：O(nm)改进的终止条件：d都不改变加速：用dijkstra得到初始d[]一个例子24小时营业的超市需要一批出纳员来满足它的需求每天的不同时段需要不同数目的出纳员例如：午夜时只需一小批，而下午则需要很多）经理已经提供你一天里每一小时需要出纳员的最少数量——R(0),R(1),…,R(23)。R(0)表示从午夜到午夜1:00需要出纳员的最少数目，R(1)表示上午1:00到2:00之间需要的…每一天，这些数据都是相同的。有N人申请这项工作每个申请者i在每天24小时中，从一特定的时刻开始连续工作恰好8小时定义ti（0≤ti≤23）为上面提到的开始时刻也就是说，如果第i个申请者被录用，他将从ti刻开始连续工作8小时。计算为满足上述限制需要雇佣的最少出纳员数目在每一时刻可以有比对应的R(i)更多的出纳员在工作。图论202X朱全民图G=(V,E)图的概念单击此处添加正文，文字是您思想的提炼，请尽量言简意赅地阐述观点。图的基本概念单击此处添加正文，文字是您思想的提炼，请尽量言简意赅地阐述观点。有向图、顶点、入度、出度、弧、环单击此处添加正文，文字是您思想的提炼，请尽量言简意赅地阐述观点。无向图、边、路径、顶点的度、邻接单击此处添加正文，文字是您思想的提炼，请尽量言简意赅地阐述观点。简单图、完全图单击此处添加正文，文字是您思想的提炼，请尽量言简意赅地阐述观点。平面图、二分图图的存储结构邻接矩阵graph=Recordvex:array[1..vtxptr]ofvertex;arc:array[vtxptr,vtxptr]ofvertex;邻接表表节点typearcptr=^arcnode;arcnode=record