Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

疑问:dijkstra算法 求单源点最短路径

Posted by 15000 at 2009-10-17 12:59:27 on Problem 2387
一般的dijkstra算法都是
int edge[N][N];//记录边的权值
bool v[N];//判断点是否已有最短路径
int dist[N];//记录点的最短路径

对于更新当前的最短路径,通常都是
v[u]=ture;//v以有最短路径
 for(j=1;j<=n;j++)
          if(v[j]==false && edge[u][j]+dist[u]<dist[j])
            dist[j]=edge[u][j]+dist[u];


如果我现在改成
int edge[N][N];//记录边的权值
int dist[N];//记录点的最短路径,当dist[i]==0时表明点i还没有最短路径

对于更新当前的最短路径:
假设dist[u]=100;//u已有最短路径
for(j=1;j<=n;j++)
     if(dist[j]==0)//j还没有最短路径
     { 
           if(dist[u]+edge[u][j]<edge[单源点的那个点][j])
               edge[单源点的那个点][j]=dist[u]+edge[u][j];
     }
这样做不行吗?
         
           
     


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator