1.初始化令S={v0}, T={剩下顶点} V为全部顶点集合
2.d[i]初值:若 [HTML_REMOVED]存在,那么就把d[i]的值设置为权值,否则就为无穷
3.从T中迭代找出一个距离v0距离最小的顶点vj加入s,根据新加入的顶点vj更新d[i]的值
4.对T中的顶点进行修改
5.重复上述,直至 S = V
错误代码 晚上找一下错误点
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
int dis[N][N] = {9999};
int n;//几个顶点
int m;//几条边
int d[N];
int v[N];//是否已经放在s集合中
int find()//找距离最小的点,贪心体现在这
{
int ma = 9999;
int temp = 0;
for(int i = 2; i <= n; i ++)
{
if(d[i] < ma) {
ma = d[i];
temp = i;
}
}
return temp;
}
int full()
{
int a = 1;
for(int i = 2; i <= n; i ++)
{
a = a * v[i];
}
return a;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++)
{
int j, k, l;
scanf("%d%d%d", &j, &k, &l);
dis[j][k] = l;
}
for(int i = 2; i <= n; i ++)
{
if(dis[1][i] < 9999) d[i] = dis[1][i];//最初的数据进去
else d[i] = 9999;
}
v[1] = 1;//第一个顶点放进去了
int t = full();//返回s集合是否已经包含所有顶点
int p = find();//找到距离1顶点最小的顶点
v[p] = 1;//把找到的顶尖加入集合
t = full();
while(!t)//s集合是否已经全部包含所有顶点
{
for(int i = 2; i <= n; i ++)
{
if(d[i] > d[p] + dis[p][i]);
d[i] = d[p] + dis[p][i];
}
p = find();
v[p] = 1;
t = full();
}
return 0;
}
$orz$