试探性 并不是指查找相邻的最短的距离的点。  

假设 在上面的图中  v3--v5的权值改为4的时候

根据你上面的思路， 到v4的时候 选个最短的， v3被加入到CLOSE中， 到v3的时候 OPEN中只有v5 ，得出来的结果是11，都是按照最小的权值来操作的。  这样不存在什么试探， 因为没有比较在新的路径和原来的路径之间。

能不能再帮我看看这代码
这是HDU 1874的一道题 http://acm.hdu.
代码如下

#include<stdio.h> 
#include<string.h> 
#define M 205 
#define INF 0xfffffff 

 
int dis[M]; 
int G[M][M]; 
int que[M*M]; 
bool v[M]; 
int n,m; 

 
int min(int a,int b) 
{ 
    if(a<b) return a; 
    return b; 
} 

 
void SPFA(int u) 
{ 
    int l=0,r=0; 
    int i,p; 
    memset(v,false,sizeof(v)); 
    for(i=0;i<n;i++) 
        dis[i]=INF; 
    que[r++]=u; 
    dis[u]=0; 
    v[u]=true; 
    while(l<r)                              //这里的r不是等于1的吗？怎么进行运行呢？
    { 
        p=que[l++]; 
        v[p]=false; 
        for(i=0;i<n;i++) 
            if( dis[i]>dis[p]+G[p][i]) 
            { 
                dis[i]=dis[p]+G[p][i]; 
                if(!v[i]) 
                { 
                    v[i]=true; 
                    que[r++]=i; 
                } 
            } 
    } 
} 

 
int main() 
{ 
    int i,j; 
    int s,t; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        for(i=0;i<n;i++) 
            for(j=0;j<n;j++) 
                G[i][j]=INF; 
        while(m--) 
        { 
            int a,b,c; 
            scanf("%d%d%d",&a,&b,&c); 
            G[a][b]=G[b][a]=min(G[a][b],c); 
        } 
        scanf("%d%d",&s,&t); 
        SPFA(s); 
        if(dis[t]!=INF) 
            printf("%d\n",dis[t]); 
        else printf("-1\n"); 
    } 
    return 0; 
} 

你所说的试探性比较是在哪段代码怎么实现的呢？
再麻烦你一次了
还有其中有个 while(l<r)  此时r不是等于1吗？不会执行下面的代码的吧？

自己帮顶下

//ss.c
#include <stdio.h>
#include <assert.h>

#define MAX_SIZE    (205)//结点的最大值
#define INF            (0xfffffff)//表示无穷

int Graphic[MAX_SIZE][MAX_SIZE];//无向图
int Value[MAX_SIZE];
int val_n;//结点数
int val_m;//弧的数量

//初始化图的状态 0 成功   非零 失败
int init_g(void)
{
    int i=0;
    int nVs, nVd, nVv;

    for (i=0; i<MAX_SIZE; ++i)
    {
        int j=0;

        Value[i] = INF;
        for (; j<MAX_SIZE; ++j)
        {
            Graphic[i][j] = INF;
        }
    }

    //printf("输入结点数_弧的数量: ");
    scanf_s("%d%d", &val_n, &val_m);
    //判断输入是否正确
    if (val_m > (val_n*(val_n-1))/2)
    {
        return -1;
    }

    if (0>=val_m || val_m>1000 ||
        val_n<=0 || val_n>200)
    {
        return -1;
    }

    //printf("输入分别输入(Vx,Vy,value):");Vx!=Vy
    for (i=0; i<val_m; ++i)
    {
        scanf_s("%d%d%d",&nVs, &nVd, &nVv);
        if (nVs == nVd || nVv<=0 || nVv>=1000)
        {
            return -1;
        }
        Graphic[nVs][nVd] = Graphic[nVd][nVs] = nVv;
    }

    return 0;
}

//
int min_index(int flag[])
{
    int min = INF, j=-1, i;

    for (i=0; i<val_n; ++i)
    {
        if (!flag[i] && min>Value[i])
        {
            min = Value[i];
            j = i;
        }
    }
    return j;
}

//
int SPFA(const int n_Vs, const int n_Vd)
{
    //n_Vs到达当前的某点v时  是最短的  则不存在还有路线必这条还短的
    int nVector = n_Vs;
    int flag[MAX_SIZE] = {0};

    flag[n_Vs] = 1;
    Value[n_Vs] = 0;

    while (n_Vd != nVector)
    {
        int i;

        for (i=0; i<val_n; ++i)
        {
            if (flag[i])
            {
                continue;
            }
            if (Value[i] > Value[nVector] + Graphic[nVector][i])
            {
                Value[i] = Value[nVector] + Graphic[nVector][i];
            }
        }

        nVector = min_index(flag);

        if (-1 == nVector)
        {
            return -1;
        }

        flag[nVector] = 1;

    }

    return 0;

}

int main(int argc, char *argv[])
{
    int nVs, nVd;
    int nRetCode = init_g();
    assert(nRetCode == 0);

    //printf("输入起点和终点: ");
    scanf_s("%d%d", &nVs, &nVd);
    assert(nVs>=0 && nVs<val_n && nVd>=0 && nVd<val_n);

    if (-1 == SPFA(nVs, nVd))
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", Value[nVd]);
    }

    return 0;
}

只测试了三个例子  所以不能确保没错误

非常感谢，我仔细拜读去了！

http://acm.hdu.  这才是真题

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Line
{
    int v1;
    int len;
    int cost;
    int v2;
};

struct DP
{
    int len;
    int cost;
};

int main()
{
    int m,n;
    int i,j,k;
    while(scanf("%d%d",&n,&m) && m+n)
    {
        vector<Line> g[1001];
        DP dp[1001];
        for(i = 0;i<=n;i++)
            dp[i].cost = dp[i].len = 0x7FFFFFFF;
        for(i = 0;i<m;i++)
        {
            Line a;
            scanf("%d%d%d%d",&a.v1,&a.v2,&a.len,&a.cost);
            g[a.v1].push_back(a);
            a.v1 ^= a.v2;a.v2 = a.v1^a.v2;a.v1 ^= a.v2;
            g[a.v1].push_back(a);
        }
        queue<int> q;
        bool inque[1001] = {0};
        int s,e;
        scanf("%d%d",&s,&e);
        dp[s].cost = dp[s].len = 0;
        q.push(s);
        inque[s] = true;
        while(!q.empty())
        {
            int temp = q.front();
            q.pop();
            inque[temp] = false;
            for(i = 0;i<g[temp].size();i++)
            {
                int rv = g[temp][i].v2;
                int l = g[temp][i].len;
                int c = g[temp][i].cost;
                if(dp[rv].len == dp[temp].len+l)
                {
                    if(dp[rv].cost > dp[temp].cost+c)
                        dp[rv].cost = dp[temp].cost+c;
                    if(!inque[rv])
                    {
                        q.push(rv);
                        inque[rv] = true;
                    }
                }
                else if(dp[rv].len > dp[temp].len+l)
                {
                    dp[rv].len = dp[temp].len+l;
                    dp[rv].cost = dp[temp].cost+c;
                    if(!inque[rv])
                    {
                        q.push(rv);
                        inque[rv] = true;
                    }
                }               
            }
        }
        printf("%d %d\n",dp[e].len,dp[e].cost);
    }
    return 0;
}

/*
3 3
1 2 5 2
2 3 4 2
1 3 9 6
1 3
*/