浅析最短路径.pptVIP

最短路径 最短路径 在一个无向连通网络图中，从某个顶点到另外一个顶点往往有多条路径，在这些路径里面，边的权值之和最小的路径称为最短路径。通常出发的顶点也称为源点，到达的顶点称为终点 在网络中，从源点到其余各顶点的最短路径问题，称为单源最短路径问题 最短路径问题也对应生活中一些实际问题，像旅游问题，运输问题等等 最短路径 在求最短路径问题中，当所有的权值都大于零的时候，可以用迪杰斯特拉算法 迪杰斯特拉思想：按照从已构造的最短路径的基础上，逐步去构造其他点到源点的最短路 起始条件：在除了源点之外其他的顶点中，可以马上确定一个顶点到源点的最短路径 衔接过程：将网络中所有顶点分成两组，一组是源点到它们的最短路径已经确认的，另一组是源点到他们的最短路径尚未确认的。那么如何从未确认的顶点中找出能加入到确认顶点行列中去呢？ 思考：在有向图中，能不能用迪接斯特拉算法？如何打印源点到某点最短路的路径呢？ 练习 最短路（short.c/short.in/short.out）输入一个无向网络，输出其中2个顶点之间的最短路径长度输入文件第一行为n和m，表示有n个顶点和m条带权边，其中顶点编号是从1到n，接下来有m行，每行三个整数，分别表示两个顶点编号和对应边的权值，再接下来有一行，两个整数表示要求的最短路径的两个顶点编号输出文件就一行，即两个顶点间的最短路径长度（权值和）样例输入：4 51 2 21 3 12 3 22 4 13 4 61 4样例输出：3 * * *