单源最短路径的Dijkstra算法.doc

精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
撰写人：___________日 期：___________
----------------------
void Dijkstra(int n, int v, int dist[], int prev[], int c[][LEN])
{
bool s[LEN]; // 判断是否已存入该点到S集合中
for (int i = 1; i <= n; i++)
{
dist[i] = c[v][i];
s[i] = false; //初始都未用过该点
if (dist[i] == MAX)
prev[i] = 0; //表示v到i前一顶点不存在
精品范文模板 可修改删除

免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
else
prev[i] = v;
}
dist[v] = 0;
s[v] = true;
for (int i = 1; i < n; i++)
{
int temp = MAX;
int u = v;
for (int j = 1; j <= n; j++)
if ((!s[j]) && (dist[j] < temp)) //j不在s中，v到j距离不在为无穷大
{
u = j; // u保存当前邻接点中距离最小的点的号码
temp = dist[j];
}
s[u] = true;
k++;
b[k] = u;
cout << "----------------------------------------------------------" << endl;
cout << "迭代次数：" << i << endl;
cout << "顶点为：";
精品范文模板 可修改删除

免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
cout << v << "\t";
for (int i = 1; i <= k; i++)
cout << b[i] << "\t";
cout << endl;
for (int j = 1; j <= n; j++)
if ((!s[j]) && c[u][j] < MAX)
{
int newdist = dist[u] + c[u][j];
if (newdist < dist[j])
{
dist[j] = newdist; //更新dist
prev[j] = u; //记录前驱顶点
}
}
cout << "单源路径分别为：" << endl;
for (int i =