3> 定义 distance 数组[顶点值]=最短路径长度,作用是记录最短路径长度。
4> 定义 goal[V_N+1]={0};用来记录该顶点是否被访过,1 或 0 表示。
5> 以上声明完毕,将其 path_cost 信息注入到 graph_matrix。
6> 根据起点 k,在 graph_matrix 中找出起点为 k 的值并用 distance 记录,
即 graph_matrix[k][i],i 为循环量。
7> 将当前原始点 k 到 k 的最短路径长度赋为 0,goal[k]=1 即已选择过。
重点算法:
1> 找出与 k 为起点的所有终点的最短路径 short_distance 及终点值
short_vertex;条件是与之指向的终点还没选择过。
2> 此时将此点标记已选择过。
3> 找出当前最短路径+以前顶点做起点的所有终点的最短路径,条件是
与之当前终点没被选择过。
重复 123 步。
*/
/*注意:此图为有向图*/
#include<stdio.h>
#define INFINITE 9999 //无穷,或是不能到达的顶点
#define V_N 6 //6 个顶点
#define E_N 10 //8 条边
#define BEGIN 1 //从 BEGIN 起点
#define END 6 //访问的有 END 个终点
int graph_matrix[V_N+1][V_N+1]; //下标从 1 开始,图数组
int distance[V_N+1]; //下标从 1 开始,路径长度
void add_graph_matrix(int path_cost[]) //图建立-邻接矩阵