简单的Dijkstra算法运用

Dijkstra算法常用于求单源点最短路径问题

基本思想

将顶点集合V分成两个集合，一类是生长点的集合S，包括源点和已经确定最短路径的顶点；另一类是非生长点的集合V—S，包括所有尚未确定最短路径的顶点，并使用一个待定路径表，存储当前从源点V到每个非生长点V的最短路径。

 Dijkstra算法基于的存储结构

1. 图的存储结构：在算法执行过程中，需要快速求得 任意两顶点之间边的权值，所以，图采用邻接矩阵存储。
2. 辅助数组dist[n]：其表示当前所找到的从源点V到终点的最短路径长度。初态为：若从V到v有有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。若当前求得的终点为v，则进行迭代dist[i]=min{dist[i]，dist[k]+edge[k][i]} 0<=i<=n-1
3. 辅助数组path[n]：元素path[n]是一个字符串，表示当前从源点V到终点v的最短路径。
4. 集合S：若某顶点v的最短路径已经求出，则将dist[k]置为0

伪代码 

 函数定义

void Dijkstra(int v)
{
int i,k,num,dist[Maxsize]
string path[Maxsize];
for(i = 0; i < vertexNum; i++)
{
dist[i] = edge[v][i];
if (dist[i] != 100)
path[i] = vertex[v] + vertex[i];
else path[i] = " ";
}
for (num = 1; num < vertexNum; num++)
{
k = Min(dist, vertexNum);
cout<<path[k]<<dist[k];
for (i = 0; i < vertexNum; i++)
  if (dist[i] > dist[k] + edge[k][i])
{
      dsit[i] = dist[k] + edge[k][i];
      path[i] = path[k] + vertex[i];
}
dist[k] = 0;
}
}