贪心算法和分支限界法解决单源最短路径.doc

精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
撰写人：___________日 期：___________
}
cout<<endl;
}

Dijkstra(N,v,dist,prev,c);

for(int i=2; i<=N; i++)
{
cout<<"源点1到点"<<i<<"的最短路径长度为:"<<dist[i]<<"，其路径为";
Traceback(1,i,prev);
cout<<endl;
}

return 0;
}

精品范文模板 可修改删除

免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
template<class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1])
{
bool s[N+1];
for(int i=1; i<=n; i++)
{
dist[i] = c[v][i];//dist[i]表示当前从源到顶点i的最短特殊路径长度
s[i] = false;

if(dist[i] == M)
{
prev[i] = 0;//记录从源到顶点i的最短路径i的前一个顶点
}
else
{
prev[i] = v;
}
}

dist[v] = 0;
s[v] = true;

for(int i=1; i<n; i++)
{
int temp = M;
int u = v;//上一顶点

//取出V-S中具有最短特殊路径长度的顶点u
for(int j=1; j<=n; j++)
{
if((!s[j]) && (dist[j]<temp))
{
u = j
temp = dist[j];
}
}
s[u] = true;

//根据作出的贪心选择更新Dist值
for(int j=1; j<=n; j++)
{
if((!s[j]) && (c[u]