【アルゴリズムスラグの逆襲の道】今日の問題はなんと図があります!

        ！！         ！！           ！！！

             ，       ！！！

単一ソースの最も短絡的な問題は出発点を固定し、他のすべての点で最も短絡的な問題を求めることであり、終点も固定的な問題を含む.
1-Bellman-Fordアルゴリズム

//       （BELLMAN-FORD  ） 

struct edge{int from,to,cost};   //   from    TO    cost   

edge es[MAX_E];  //  

int d[MAX_v]; //     

int V,E;    //V    ，E    

//     s           

void shortest_path(int s)
{
    for(int i=0;i<V;i++)  d[i]=INF;
    d[s]=0;
    while(true)
    {
        bool update=false;
        for(int i=0;i<E;i++)
        {
            edge e=es[i];
            if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost)
            {
                d[e.to]=d[e.from]+e.cost;
                update=true;
            }
        }
    if(!update) break; 
    }   
} 

//    true     
bool find_negative_loop()
{
memset(d,0,sizeof(d));

for(int i=0;i<V;i++)
for(int j=0;j<E;j++)
{
    edge e=es[j];
    if(d[e.to]>d[e.from]+e.cost)
    {
        d[e.to]=d[e.from]+e.cost;
        //   n      ，      
        if(i==V-1) return true; 
    }
}   
return false;
} 

書き終わった瞬間、卵が痛くて、木があります.
2-Dijlstraアルゴリズム(wufajiejeeは図中の負の側面がある問題を解決できません)
(1)最短距離が決定された頂点を見つけ、隣接する頂点の最短距離をそれから更新する.(2)今後はもう1の「最短距離が確定した頂点」に関心を持つ必要はない.

int cost[MAX_V][MAX_V];  //csot[u][v]   e=(u,v)   （         INF) 
int d[MAX_V];           //  s        
bool used[MAX_V];       //        
int V;                  //   
//    s           
void dijkstra(int s)
{
    fill(d,d+V,INF);
    fill(used,used+V,false)
    d[s]=0;

    while(true)
    {
        int v=-1;
//                      
        for(int u=0;u<V;u++)
        {
            if(!used[u]&&(v==-1||d[u<d[v]]))
            v=u;
        }
        if(v==-1)break;
        used[v]=true;

        for(int u=0;u<V;u++)
        {d[u]=min(d[u],d[V]+cost[v][u]);} 
    }
} 

まずここに行きましょう.夏休みの目標はまず検索、dp、画論をやることです.