大话数据结构—(六)最短路径算法

1.Dijkstra算法 Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题,结合图1举个例子,从V1到V2的最短路径,并不是直接连接V1,V2,而是先经过V0再到V2,好,下面一起来看代码。 #define MAXVEX 9 #define INFINITY 65535 typedef int Patharc[MAXVEX];//用于存储最短路径下标的数组 typedef int ShortPathTable[MAXVEX];//用于存储到各点最短路径的权值和 //Dijkstra算法,求有向网G的v0顶点到其余顶点v最短路径P[v]即带权长度D[v] //P[v]的值为前驱