随笔 - 87  文章 - 279  trackbacks - 0
<2024年4月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211878
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

单源最短路径Dijkstra

 

/*
 *    beg : 起点;
 *  end : 终点;
 *  n : 顶点个数;
 *  g : 邻接矩阵, 为全局变量, 下标(1, 1)起;
  */

int  pre[MAXN];
 int  dijkstra( int  beg,  int  end,  int  n)
 {
     int  i, j, u, min;
     int   * dist  =   new   int [n + 1 ];
     int   * visit  =   new   int [n + 1 ];

     for  (i = 1 ; i <= n; i ++ )  {
        dist[i]  =  MAXNUM;
        visit[i]  =   false ;
    }

    dist[beg]  =   0 ; pre[beg]  =   - 1 ;
     for  (i = 0 ; i < n; i ++ )  {
        min  =  MAXNUM;
         for  (j = 1 ; j <= n; j ++ )  {    
             if  (min  >  dist[j]  &&   ! visit[j])  {
                u  =  j;
                min  =  dist[j];
            }
        }
         if  (min  ==  MAXNUM)  break ;
        visit[u]  =   true ;
         for  (j = 1 ; j <= n; j ++ )  {
             if  ( ! visit[j]  &&  dist[j]  >  dist[u] + g[u][j])  {
                dist[j]  =  dist[u] + g[u][j];
                pre[j]  =  u;
            }
        }
         if  (u  ==  end)  break ;        
    }

     return  dist[end];
}
posted on 2006-08-09 14:56 豪 阅读(317) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 豪 Powered by: 博客园 模板提供：沪江博客