| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
疑问:dijkstra算法 求单源点最短路径一般的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator