有向图图中任何两个可到达的顶点之间最短路径以及相应的长度
Dijkstra算法 和Floyd算法
1 #include "iostream" 2 #include "vector" 3 #include "stdlib.h" 4 using namespace std; 5 6 const int MaxNumVertex = 20; //最大顶点数 7 const int infinity = 65535;//无穷大 8 typedef int elementtype; //elementtype 为int 型 9 class graph{ 10 public: 11 graph(); 12 ~graph(); 13 elementtype insertvertex(elementtype v); //在图中增加一个顶点 14 elementtype insertedge(elementtype v,elementtype u,elementtype weight);//在图中增加一条从v顶点到u顶点的弧 15 elementtype firstadj(elementtype v);//求图g中顶点v的第一个邻接点 16 elementtype nextadj(elementtype v,elementtype m);//求图中顶点v的m邻接点之后的邻接点 17 elementtype degreeout(elementtype v);//求图中顶点v的出度数 18 elementtype FindDegreeout(elementtype oud[]);//各顶点的入度存放于出度数组中 19 elementtype Dijkstra(elementtype v0);//求解从v0到各顶点的最短路径 20 elementtype Floyd();//各顶点之间最短路径以及长度 21 elementtype create();//创建图 22 int CurrentVertex;//当前顶点数 23 24 private: 25 elementtype vertex[MaxNumVertex];//顶点表 26 elementtype edge[MaxNumVertex][MaxNumVertex];//图中弧的类型 27 28 }; 29 30 /* 31 *初始化 32 */ 33 graph::graph() 34 { 35 CurrentVertex = 0; 36 int i,j; 37 for (i=MaxNumVertex-1;i>=1;i--) 38 { 39 for (j=MaxNumVertex-1;j>=1;j--) 40 { 41 edge[i][j] = infinity; 42 43 } 44 } 45 46 } 47 48 /* 49 *在图中增加一个顶点 50 */ 51 elementtype graph::insertvertex(elementtype v) 52 { 53 //判断这个顶点是否已经存在 54 int i; 55 bool flags = true; 56 for(i=1; i<=CurrentVertex; i++) 57 { 58 if(vertex[i]==v) 59 { 60 flags = false; 61 break; 62 } 63 } 64 65 if(flags) 66 { 67 CurrentVertex++; 68 vertex[CurrentVertex] = v; 69 }else{ 70 cout< <<"顶点已经存在!"< "< <<"这条弧弧已经存在!"< 
