单源最短路径---贪心法实现(Dijkstra算法)

//贪心法解决单源最短路经问题
//定点v表示源，a为图的邻接矩阵，dist[i]表示源到顶点i的最短路经长度
//prev[i]表示最短路经中i顶点的前驱顶点

#define MAX_DISTANCE 100000


void Shortest_Path(int v,float **a,float dist[],int prev[],int n){
  if(v < 1 || v > n) return;
  bool *s = ( bool* )malloc( n * sizeof(bool) );//记录是否为s集合中的
//元素
  for(int i = 0; i < n; i++)//初始化
  {
   dist[i] = a[v][i];
   s[i] = false;
   if(dist[i] < MAX_DISTANCE)
    prev[i] = v;
   else
    prev[i] = 0;
  }
  dist[v] = 0;
  s[v] = true;

  for(int i = 0; i < n; i++)  {
    float temp = MAX_DISTANCE;
    int u = v;
    for(int j = 0; j < n; j++)//选择s集合外元素中到源v最小的顶点,并记录
     //该点和最小值
   {
    if(!s[j] && dist[j] < temp)
    {
             u = j;
             temp = dist[j]; 
    }
   }
      
   s[u] = true;//将u加入s集合

   for(int j = 0; j < n; j++) //更新dist的值,使dist[i]为当前的最优解
   {
    if(!s[j] && a[u][j] < MAX_DISTANCE)
    {
     float newdist = dist[u] + a[u][j];
     if(newdist < dist[j])
     {
      dist[j] = newdist;
      prev[j] = u;
     }
    }
   }
  }
}

评论

1 楼 fuliang 2007-04-10  

你觉得不是贪心法么？前半段选择s集合外元素中到源v最小的顶点（一步的最优解）, 然后把这个点加入s集合中。
贪心法的特点是什么？有最优解结构，它与动态规划的区别在于：他一次就能排除掉所有的次优解，从而确定一步的最优解。