编写的迪杰斯特拉算法求最短路径，运行不正确？

编写的迪杰斯特拉算法求最短路径，运行不正确？

鉴于最小生成树和最短路径的dijkstra是相似的，我把它们合到一块了，另外下面附了一个用堆优化的dijkstra（优先队列）的代码，看看吧。

最小生成树的普利姆算法和求最短路径的dijkstra算法
算法思想：
1.、先将出发点（对最小生成树来说可以是任意一点）放入集合s中（s为元素为图的顶点的集合，记录已经解决的顶点）。
2、找到s外的所有点到s的距离（即到s中所有点的距离的最小值）最小的点，把这一点加入s集合。
3、由于新加入的一个点会使某些点到s的距离更短，更新s外的其他点到集合s的距离（如果可以更短，则更新之）。
4、返回执行第2步，直到所有的点都加入s中。
注：第二步找到的最短距离会逐步增加，所以此算法也可以解决例如第K远的城市这种问题
算法代码：
int const MAXN = 100;
int i,j;

int n; //记录图的顶点个数

int edge[MAXN][MAXN]; //记录各边权值, 默认无向并且已知，两点之间无边则记为无穷大

int dist[MAXN]; //记录当前各个点到集合s的最小距离，在运行过程中不断更新

int s[MAXN] = {0}; //记录已经解决的点的下标,标志着该顶点是否加入最小生成树

//初始化，假设各边权值已知，出发点为0
for(i = 0; i < n; i++)
{
dist[i] = edge[0][i];
}


s[0] = 1;

for(i = 0; i < n - 1; i++)//循环n-1次将剩余的n-1个点加入生成树
{

int min = inf; // inf 为可能的最大值
int u = 0; // 记录距离s最短的顶点的下标
for(j = 0; j < n; j++)
{
if(!s[j] && dist[j] < min)
{
min = dist[j];
u = j;
}
}
s[u] = 1;


for(j = 0; j < n; j++)
{
if(!s[j] && edge[u][j] < dist[j])
dist[j] = edge[u][j];
}



for(j = 0; j < n; j++)
{
if( !s[j] && dist[u] + edge[u][j] < dist[j])
dist[j] = dist[u] + edge[u][j];
}

}

附：


#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 110;

int head[MAXN],size;
int dist[MAXN];
int n;

struct enode{
int v,cost,next;
enode(){}
enode(int _v,int _cost):v(_v),cost(_cost){}
enode(int _v, int _cost, int _next):v(_v), cost(_cost), next(_next){}
bool operator < (const enode &t) const{
return cost > t.cost;
}
};
enode edges[MAXN*MAXN];

void add_edge(int u,int v,int cost){
edges[size] = enode(v,cost,head[u]);
head[u] = size++;
}

int init(){
int m,u,v,c;
memset(head,-1,sizeof(head));
size = 0;
scanf("%d%d",&n,&m); //输入顶点数和边数
if(m == 0 && n == 0)return 0;
for(int i = 0; i < m; i++){
scanf("%d%d%d",&u,&v,&c); //输入边的两个顶点和边的权值
add_edge(u-1,v-1,c);
add_edge(v-1,u-1,c);
}
return 1;
}

void Dijkstra(int st){

memset(dist,0x3f,sizeof(dist));
dist[st] = 0;

priority_queue < enode > q;
q.push( enode(st,0) );
while ( !q.empty() ){

enode top = q.top();
q.pop();

if(top.cost != dist[top.v]) continue;

int u,v;
u = top.v;
for(int i = head[u] ;i != -1; i = edges[i].next){
v = edges[i].v;
if ( dist[v] > dist[u] + edges[i].cost ){

dist[v] = dist[u] + edges[i].cost;
q.push( enode(v,dist[v]) );
}
}
}
}

int main(){
while( init() ){
Dijkstra(0);
printf("%d\n",dist[n-1]);
}
return 0;
}