计算机算法设计与分析 (四) 贪心算法--单源最短路径
程序员文章站
2022-05-23 09:57:59
...
1.Dijkstra算法是解决单源最短路径的一个贪心算法。给定一个带权有向图G=(V,E),其中每条边的权都是非负实数,另外,还给定V中的一个顶点,称为源。现在要计算源到其他各个顶点的最短路长度。这里的路的长度指的是路上各边权之和。
Dijkstra算法可描述如下,其中输入的带权有向图是G=(V,E),顶点v是源。c是一个二维数组,c[i][j]表示边(i,j)的权。当(i,j)之间无直接的边连接时,c[i][j]是一个大数。dist[i]表示当前从源点到顶点i的最短特殊路径长度。
template<class Type>
void Dijkstra(int n, int v,Type dist[][],int prev[],Type **c)
{
bool s[n+1];
for(int i=1;i<=n;++i)
{
dist[i]=c[v][i];
s[i]=false;
if(dist[i]==Int_Max) prev[i]=0;
else prev[i]=v;
}
dist[v]=0;
s[v]=true;
for(int i=1;i<n;++i)
{
int temp =maxint;
int u=v;
for(int i=1;i<n;i++)
{
if(dist[j]<temp&&!s[i])//选出当前剩余点中距离v最近的点
{
u=j;
temp=dist[j];
}
}
s[u]=true
for(int j=1;j<=n;++j)//更新dist数组
{
if(!s[i]&&c[u][j]+dist[u]<dist[j])
{
dist[j]=c[u][j]+dist[u];
prev[j]=u;
}
}
}
}
算法的正确性和复杂性
1)贪心选择性质
dijkstra算法所做的贪心选择是从V-S中选择具有最短特殊路径的顶点u,从而确定源到u的最短路径长度
2)最优子结构
不论算法中dist[u]是否变化,它总是关于当前顶点集S到v的特殊最短路径长度
上一篇: 算法讲解--二分查找、大O表示法
下一篇: 宽度优先搜索 最短路径