一、Dijkstra算法(贪心地求最短距离的算法)
在此算法中，我按照自己的理解去命名，理解起来会轻松一些。
#define MAXSIZE 100#define UNVISITED 0#define VISITED 1#define INFINITY 66666typedef struct tool { int visited[MAXSIZE]; /*是否已访问的数组,visited[i]表示顶点i已经访问，也就是到顶点i的最短距离已求出*/ int known_shortest_distance[MAXSIZE]; /*已知的最短距离数组。known_shortest_distance[i]代表从V0到Vi的最短距离*/ int previous_vertex[MAXSIZE]; /*previous_vertex[i]=j,代表：在从V0到Vi的最短路径上，顶点i的前一个顶点是顶点j*/} Tool;typedef struct gragh { int num_of_vertexes; int adjacent_matrix[MAXSIZE][MAXSIZE];} Gragh;void init_tool(Gragh g, Tool &t) { int i = 0; for(i = 0; i < g.num_of_vertexes; i++) { t.visited[i] = UNVISITED; t.known_shortest_distance[i] = g.adjacent_matrix[0][i]; t.previous_vertex[i] = 0; }}void dijstra_shortest_distance(Gragh g, Tool &t) { int i, j, x; //循环变量 int min_distance, x_index; /*min_distance存储的是当前已知的最短距离数组中从V0到Vx最小的距离; x_index存储的Vx的下标*/ init_tool(g, t); for(i = 0; i < g.num_of_vertexes; i++) { min_distance = INFINITY; for(x = 0; x < g.num_of_vertexes; x++) { if(!t.visited[x] && t.known_shortest_distance[x] < min_distance) { min_distance = t.known_shortest_distance[x]; x_index = x; } } /*通过上面一个循环，最短距离数组中的最小值就是min_distance; 该顶点的下标就是x_index; 在当前没有访问且以V0为起点距离最短的顶点中， 这个点的下标就是x_index.*/ t.visited[x_index] = VISITED; for(j = 0; j < g.num_of_vertexes; j++) { if(!t.visited[j] && (min_distance + g.adjacent_matrix[x_index][j] < t.known_shortest_distance[j])) { t.known_shortest_distance[j] = min_distance + g.adjacent_matrix[x_index][j]; t.previous_vertex[j] = x_index; } } }} 如果要求任意两点之间的最短距离：只需在外层加一层循环，把最短距离数组和previous_vertex数组变成二维数组即可。
输出从V0到Vi的最短距离和完整路径：
#includevoid print_path(Tool &t, int dest) { int i = dest; stack s; cout << "从V0到V" << i << "的最短距离:" << t.known_shortest_distance[i] << endl; while(t.previous_vertex[i] != 0) { s.push(t.previous_vertex[i]); i = t.previous_vertex[i]; } cout << "从V0到V" << i << "的路径:"; cout<<"V0"; while(!s.empty()) { cout << "->V" << s.top(); s.pop(); } cout << "->V" << dest;}
一、Floyd算法(不管三七二十一，先把整个图中任意两点的最短距离求出再说)
核心思想：对图中任意两个顶点(即下面代码中的j和k),如果能在其他顶点中(也就是下面代码中的i，在原始版本中，i和j,k可以相同)找到一个顶点i，使得顶点j到顶点i的距离加上顶点i的距离到顶点k的距离比直接从顶点j到顶点k的距离短，那么，就修改顶点j到顶点k的距离。
typedef struct floyd_tool { int known_shortest_distance[MAXSIZE][MAXSIZE]; /*已知的最短距离数组。known_shortest_distance[i][j]代表从Vi到Vj的最短距离*/ int path_matrix[MAXSIZE][MAXSIZE]; /*path_matrix[i][j]=k,代表：在从Vi到Vj的最短路径上，要经过顶点k; 用k代替i,直到path_matrix[k][j]=j*/} FloydTool;void init_floyd_tool(FloydTool &ft, Gragh g) { for(int i = 0; i < g.num_of_vertexes; i++) { for(int j = 0; j < g.num_of_vertexes; j++) { ft.known_shortest_distance[i][j] = g.adjacent_matrix[i][j]; ft.path_matrix[i][j] = j; } }}void floyd_shortest_distance(Gragh g,FloydTool &ft) { init_floyd_tool(ft,g); for(int i = 0;i < g.num_of_vertexes; i++){ for(int j = 0;j < g.num_of_vertexes;j++){ for(int k = 0;k < g.num_of_vertexes;k++){ if(ft.known_shortest_distance[j][k] > ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]){ ft.known_shortest_distance[j][k] = ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]; ft.path_matrix[j][k] = ft.path_matrix[j][i]; } } } }}
改进版：
改进依据：由上面初始版本的思想可知，对于任意两个顶点j和顶点k，如果顶点j和顶点i是同一个，那么，最里面一层的比较相当于是D和0+D在比，显然，这是没必要的。或者，如果j和i不相等，但是i不是j的邻接点，那么j到i的距离就是“无穷大”，很显然，通过这个桥梁i是不可能缩短j到k的距离的。所以，有了第一个if；同理，第二个if也是这么来的。然后，初始版本中，最里面两层循环的循环变量都是从0开始的，但是因为我们考虑的是无向图，j到k的距离和k到j的距离是一样的，所以，我在改进版本中减去了重复求k到j的距离。
void floyd_shortest_distance(Gragh g,FloydTool &ft) { init_floyd_tool(ft,g); for(int i = 0;i < g.num_of_vertexes; i++){ for(int j = 0;j < g.num_of_vertexes;j++){ if(j == i || ft.known_shortest_distance[j][i] == INFINITY)continue; for(int k = j + 1;k < g.num_of_vertexes;k++){ if(k == i || ft.known_shortest_distance[k][i] == INFINITY)continue; if(ft.known_shortest_distance[j][k] > ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]){ ft.known_shortest_distance[j][k] = ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]; ft.path_matrix[j][k] = ft.path_matrix[j][i]; } } } }}
输出最短距离和完整路径：
void print_path(FloydTool &ft,int orig,int dest) { cout << "从V"< <<"到V"< << "的最短距离:" << ft.known_shortest_distance[orig][dest] << endl; cout << "从V"< <<"到V"< <<"的路径:"; cout<<"V"< V"< V" << dest;}