山大公交线路上优化路径的查询实验报告 - 图文

int i=1; while(i

17

for(int j=0; j

18

} void Dijkstra(int n, int v, double *dist, int *prev, double **c) { bool s[range+1]; // 判断是否已存入该点到S集合中 for(int i=1; i<=n; ++i) { dist[i] = c[v][i]; s[i] = 0; // 初始都未用过该点 if(dist[i] == NoEdge) prev[i] = 0; else prev[i] = v; } dist[v] = 0; s[v] = 1; // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中 // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 // 注意是从第二个节点开始，第一个为源点 for(int i=2; i<=n; ++i) { int tmp = NoEdge; int u = v; // 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!s[j]) && dist[j]

19

// 查找从源点v到终点u的路径，并输出 void ReDijkstra(int n, int v, double *dist, int *prev, double **c) { bool s[range+1]; // 判断是否已存入该点到S集合中 for(int i=1; i<=n; ++i) { dist[i] = searchPrice(static_cast(c[v][i])); s[i] = 0; // 初始都未用过该点 if(dist[i] == NoEdge) prev[i] = 0; else prev[i] = v; } dist[v] = 0; s[v] = 1; // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中 // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 // 注意是从第二个节点开始，第一个为源点 for(int i=2; i<=n; ++i) { int tmp = NoEdge; int u = v; // 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!s[j]) && dist[j]

20