図論の最短入門

最短ルートには多くのアルゴリズムがあります.
Dijkstraとfloydの2つのアルゴリズムについてお話しします.
この2つの方法は最短経路を出力する際にpre配列を利用して,バックグラウンドする方法である.
Dijkstraは各点からソース点までの最短距離を知ることができ,dist[]配列で記録され,時間複雑度はO(n^2)である.
具体的には、次のようになります.
図中のすべての頂点Vを2つの集合Va,Vbに分割し、ソース点からuへの最短経路が決定された場合、点uは集合Vaに属し、そうでなければVbに属する.
Vbに属するすべての点の中でSからその経路長が最も短い点uを探し、uをVbから除去し、Vaに加える.
新たに決定されたu更新SからVbの各点vまでの距離は、sからuまでの距離に加えてuからvまでの直接距離が現在のsからvまでの距離よりも小さい場合、新しく生成された最短経路の長さが前に計算されたものよりも短いことを示す場合、この距離を更新する.
この操作を繰り返すと、Vbに既に点がないか、Vbの点がソース点Sから到達できないことがわかる.
Floydは各点から各点までの最短距離を求めることができ,複雑度はO(n^3)であり,動的プランニングを利用した.iからjまでの最短距離をdist[]配列で記録した.
kは1からnまでn回ループし、毎回ループ中、図中の異なる2つの点u,vを列挙し、dist[u][v]>dist[u][k]+dist[k][v]であれば、dist[u][v]=dist[u][k]+dist[k][v]、pre[u][v]=pre[k][v]を更新する.
具体的なコード:
HDu 2544最短
Dijkstra:

#include
using namespace std;
const int maxn = 10000 + 10;
int maze[maxn][maxn];
int n,m;
int dist[maxn];//    s   i     
int pre[maxn];//    ，      
void Dijkstra(int s)
{
    bool p[maxn];//        Va，   Va   Vb
    for(int i = 1;i <= n;i++)
    {
        if(i != s)
        {
            p[i] = false;
            dist[i] = maze[s][i];
            pre[i] = s;
        }
    }
    dist[s] = 0;
    pre[s] = s;
    p[s] = true;
    for(int i= 1 ;i<= n-1 ;i++)// Vb  n-1      
    {
        int mins = INT_MAX;//     Vb      S        k
        int k = 0;
        for(int j = 1;j <= n;j++)
        {
            if(!p[j] && dist[j] 

Floyd:

#include
using namespace std;
const int maxn = 100+ 10;
int maze[maxn][maxn];
int dist[maxn][maxn];
int n,m;
int pre[maxn][maxn];
void Floyd()
{
    for(int i=1;i<=n;i++)
    {
        for(int j = 1;j<= n;j++)
        {
            dist[i][j] = maze[i][j];
            pre[i][j] = i;
        }
    }
    for(int k = 1; k<= n ;k++)
    {
        for(int i=1;i <= n ;i++)
        {
            for(int j=1 ;j<= n;j++)
            {
                if(dist[i][j] >= dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j] = pre[k][j];
                }
            }
        }
    }
}
int main()
{
   while(~ scanf("%d%d",&n,&m) &&(n || m))
   {
       memset(dist,INT_MAX,sizeof(dist));
       for(int ii =1; ii <= m;ii++)
       {
           int x,y,z;
           scanf("%d%d%d",&x,&y,&z);
           maze[x][y] = z;
           maze[y][x] = z;
       }
       Floyd();
       cout<

POJ1797 Hesvy Tansport
この問題は、ソースポイント1からnまでの伝送可能な最大の重量を見つけることである.各道には定格最大の荷重がある.
アイデア:DIjstraを使用して、ソースポイントから各ポイントへの最大荷重を見つけます.

#include
#include
#include
#include

using namespace std;
const int maxn = 1000 + 10;
int maze[maxn][maxn];
int dist[maxn];//           
int n,m;

void Dijkstra()
{
    bool  p[maxn];//Va  
    int s = 1;//  
    for(int i = 1;i <=n ;i++)
    {
        if(i != s)
        {
            p[i] = false;
            dist[i] = maze[s][i];
        }
    }
    p[s] = true;
    dist[s] = INT_MAX;
    for(int i = 1;i <= n-1 ;i++)
    {
        int maxs = 0;
        int k =0;
        for(int j=1 ;j<= n;j++)// Vb              
        {
            if(!p[j] && dist[j] > maxs)
            {
                maxs = dist[j];
                k =j;
            }
        }
        if(k == 0)
            return ;
        p[k] = true;
        for(int j = 1; j <= n; j ++)
        {
            if(! p[j] && min(dist[k] , maze[k][j]) > dist[j])//             
            {
                dist[j] = min(dist[k],maze[k][j]);
            }
        }
    }
}
int main()
{
    int Tcase;
    scanf("%d",&Tcase);
    for(int ii = 1; ii <= Tcase; ii ++)
    {
        scanf("%d%d",&n,&m);
        memset(dist,0,sizeof(dist));//      0
        memset(maze,0,sizeof(maze));// i j         0
        for(int i =0 ;i