算法-单源点最短路径-Dijkstra算法

1、实验单源点最短路径一、实验目的1、深入理解贪心策略的基本思想。2、能正确采用贪心策略设计相应的算法，解决实际问题。3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容单源最短路径三、设计分析单源点最短路径Dijkstra 算法是解单源点最短路径的一个贪心算法。其基本思想是，设置 顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合当且仅当 从源点到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径， 并用数组dist记录当前每个顶点所对应的最短路径特殊长度。Dijkstra 算法每次从V-S中

2、取出具有最短特殊路长度的顶点 u,将u添加到S中，同时对数 组dist做必要的修改。一旦S包括了所有V中顶点，dist就记录了从源到所 有其它顶点之间的最短路径长度。存在一个带权有向图。四、算法描述及程序#include "stdafx.h"#include "iostream” using namespace std;#define N 5#define MAX 1000int edge17 = 1, 1, 1,2, 3, 4. 4 );int edge27 = 2, 5, 4, 3, 5, 3, 5 ;int length7 = 10, 100, 30, 50

3、, 10, 20, 60 ;int cNN;template<class T>void Dijkstra(int n, int v, T dist, int prev)bool sMAX;for (int i = 1; i <= n; i+)disti = cvi;si = false;if (disti = MAX)previ = 0;elseprevi = v;)distv = 0;sv = true;for (int i = 1; i<n; i+)int temp = MAX;int u = v;for (int j = 1; j <= n; j+)int

4、temp = MAX;int u = v;for (int j = 1; j <= n; j+) if (!sj) && (distj<temp)u = j;temp = distj;)su = true;for (int j = 1; j <= n; j+)if (!sj) && (cuj < MAX) T newdist = distu + cuj; if (newdist < distj) distj = newdist;prevj = u;)int main()int v;for (int i = 1; i < N +

5、 1; i+)for (int j = 1; j < N + 1; j+) cij = MAX;)for (int i = 0; i < 7; i+)(int m = edge1i;int n = edge2i;int Length = lengthi;cmn = Length;)int distN + 1, prevN + 1;cout << endl << ”可通行的路径："<< endl<<endl;for (int i = 1; i < N + 1; i+) (for (int j = 1; j < N

6、+ 1; j+)(if (cij < MAX) (cout << i << "-" << j <<'t' <<"距离为："cout << cij << endl;)cout << "从"<< i << "无法到达其它顶点"<< endl << endl; )cout << endl << ”请输入源点:"cin >

7、;> v;Dijkstra(N, v, dist, prev);cout << ”最短路径为："<< endl << endl;for (int i = 1; i < N + 1; i+) (if (disti<MAX&&disti>0)(cout << v << "->" << i << "的最短路径为"<<i;for (int n = previ; n != 0;) (cout << &q

8、uot;<-" << n;n = prevn;)cout << endl << "长度为"<< disti << endl << endl;) elsecout << v << "-" << i << "无最短路径"<<endl<<endl;)return 0;)五、测试与分析1d可通行的路径I12距离为t 101-4距离为 301-5 距离为：100 从1无法到西它顶点2-3 距离为；50 从2无法到演它顶点35 距离为:10 以3无法到演它顶点43 距离为：2045 距离为：60 M无法到送箕它顶点 从5无法到达其它顶点1 - 1元最短路径 >22的最短路径为2<一1 长度为10Bl - -M的最短路径为3<4<1 长度为5。1 一 M的最姮路径为4< 一 1长度为加1 -5的最短路径为5 <3 < - - 4<一 长度为6。M按任意键继续.-.六、实验总结与体会1 .用算法中数组prev记录