1.邻接矩阵实现 复杂度O(V^2)
int w[MAX_V][MAX_V]; ///w[u][v]表示边u->v的权值(不存在时是INF)
int d[MAX_V]; ///顶点s出发的最短距离
bool vis[MAX_V]; ///已经连通的点
int V; ///顶点数
///求起始点s到各个顶点的最短距离
void dij(int s)
{
fill(d,d+V,INF);
fill(vis,vis+V,false);
d[s]=0;
while(true)
{
int v=-1;
for(int u=0;u<V;u++) ///从未使用的顶点中选择一个距离最小的顶点
if(!vis[u]&&(v==-1||d[u]<d[v]))
v=u;
if(v==-1) break;
vis[v]=true;
for(int u=0;u<V;u++)
d[u]=min(d[u],d[v]+w[v][u]);
}
}
2.使用STL的优先队列实现 复杂度O(ElogV) E为边的个数
待更...