Dijkstra是具体的实现.doc

以下是具体的实现(C/C+):123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134/* About: 有向图的Dijkstra算法实现* Author: Tanky Woo* Blog: www.WuTianQ*/#include using namespace std;const int maxnum = 100;const int maxint = 999999;/ 各数组都从下标1开始int distmaxnum; / 表示当前点到源点的最短路径长度int prevmaxnum; / 记录当前点的前一个结点int cmaxnummaxnum; / 记录图的两点间路径长度int n, line; / 图的结点数和路径数/ n - n nodes/ v - the source node/ dist - the distance from the ith node to the source node/ prev - the previous node of the ith node/ c - every two nodes distancevoid Dijkstra(int n, int v, int *dist, int *prev, int cmaxnummaxnum)bool smaxnum; / 判断是否已存入该点到S集合中for(int i=1; i=n; +i)disti = cvi;si = 0; / 初始都未用过该点if(disti = maxint)previ = 0;elseprevi = v;distv = 0;sv = 1;/ 依次将未放入S集合的结点中，取dist最小值的结点，放入结合S中/ 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 / 注意是从第二个节点开始，第一个为源点for(int i=2; i=n; +i)int tmp = maxint;int u = v;/ 找出当前未使用的点j的distj最小值for(int j=1; j=n; +j)if(!sj) & distjtmp)u = j; / u保存当前邻接点中距离最小的点的号码tmp = distj;su = 1; / 表示u点已存入S集合中/ 更新distfor(int j=1; j=n; +j)if(!sj) & cujmaxint)int newdist = distu + cuj;if(newdist =1; -i)if(i != 1)cout quei ;elsecout quei n;/ 输入路径数cin line;int p, q, len; / 输入p, q两点及其路径长度/ 初始化c为maxintfor(int i=1; i=n; +i)for(int j=1; j=n; +j)cij = maxint;for(int i=1; i p q len;if(len cpq) / 有重边cpq = len; / p指向qcqp = len; / q指向p，这样表示无向图for(int i=1; i=n; +i)disti = maxint;for(int i=1; i=n; +i)for(int j=1; j=n; +j)printf(%8d, cij);printf(n);Dijkstra(n, 1, dist, prev, c);/