UC知道加 代码注释
来源：百度知道 编辑：UC知道 时间：2024/06/18 04:09:12
int Dijkstra(Graph G,int n,int s,int t, int path[])
{
int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
for(i=0;i<n;i++)
mark[i] = 0 ;
for(i=0;i<n;i++)
{
d[i]=G[s][i];
path[i]=s;
}
mark[s]=1;path[s]=0;d[s]=0;
for(i=1;i<n;i++)
{
minc=infinity;
w=0;
for(j=0;j<n;j++)
if((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
mark[w]=1;
for(j=0;j<n;j++)
if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{
d[j]=d[w]+G[w][j];
path[j]=w;
}
}
return d[t];
}
{
int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
for(i=0;i<n;i++)
mark[i] = 0 ;
for(i=0;i<n;i++)
{
d[i]=G[s][i];
path[i]=s;
}
mark[s]=1;path[s]=0;d[s]=0;
for(i=1;i<n;i++)
{
minc=infinity;
w=0;
for(j=0;j<n;j++)
if((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
mark[w]=1;
for(j=0;j<n;j++)
if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{
d[j]=d[w]+G[w][j];
path[j]=w;
}
}
return d[t];
}
谢谢
数据结构上机课上写的dijkstra代码
我以前弄的，有数据好理解点
呵呵，有点简陋，但是思想还是正确地...
#include "iostream"
using namespace std;
const int max_vertexes = 3;
const int infinity = 10001;
int graph[max_vertexes][max_vertexes]={
0,1,5,
infinity,0,2,
infinity,infinity,infinity
};
//typedef **int Graph;
int path[max_vertexes];
int n,s,t;
int Dijkstra(int G[max_vertexes][max_vertexes],int n,int s,int t, int path[])
{
int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
for (i=0;i<n;i++)
mark[i]=0;//标记是否被访问过
for (i=0;i<n;i++)
{
d[i]=G[s][i];
path[i]=s;
}
mark[s]=1;
path[s]=0;
d[s]=0;
for (i=1;i<n;i++)
{
minc=infinity;
w=0;
for(j=0;j<n;j++)
if ((mark[j]==0)&&(minc>=d[j]))
{
minc=d[j];
w=j;
}
mark[w]=1;
for (j=0;j<n;j++