16、单源最短路径
(1)Dijkstra 算法可以用来解决非负权重网络的单源点最短路径。
Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树,先用dist[]数组维护一个最短路径,dist[v]表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时,我们找一条边
最短路径 dijsktra 算法模板:
#include
usingnamespace std;
constint maxint = 9999999;
constint maxn = 1010;
intdata[maxn][maxn];//data存放点点之间的距离,
intlowcost[maxn]; //lowcost存放点到start的距离, 从0开始存放
boolused[maxn];//标记点是否被选中
intn; //顶点的个数
voiddijkstra(int start)//初始点是start的dij算法
{
int i,j;
memset(used, 0, sizeof(used));
//init
for(i = 0; i < n; i++)
lowcost[i] = data[start][i];
used[start] = true;
lowcost[start] = 0;
for(i = 0; i < n-1; i++)
{
//choose min
int tempmin = maxint;
int choose;
for(j = 0; j < n; j++)
{
if(!used[j] && tempmin >lowcost[j])
{
choose = j;
tempmin = lowcost[j];
}
}
used[choose] = true;
//updata others
for(j = 0; j < n; j++)
{
if(!used[j] &&data[choose][j] < maxint && lowcost[choose]+data[choose][j] { lowcost[j] =lowcost[choose]+data[choose][j]; } } } } intmain() { int start , i , j; cin>>n; for(i = 0; i < n; i++) for(j = 0; j < n; j++)//输入顶点信息 { cin>>data[i][j]; } cin>>start; dijkstra(start); int min = 0; for(i = 0; i < n; i++) { cout< for(i=0;i { for(j=0;j a[i][j]=MAX; for(i=0;i a[i][i]=0; while(edge_amount--) { scanf("%d%d%d",&i,&j,&w); a[i][j]=w; } Bellman_Ford(0); for(i=0;i { printf("dist:%d/t",d[i]); printf("path: %d",P[i]); printf("/n"); } } return 0; }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。