ジョンソンアルゴリズムをC言語で実現する方法

2年 ago
夏樹, 風
2 minutes

ジョンソン法とは、有向グラフにおける最短経路問題を解決するアルゴリズムです。その基本思想は、グラフを変換して元の負の重みの辺を非負の重みに変換してから、ダイクストラ法またはベルマンフォード法を利用して最短経路を解くことです。

ジョンソンアルゴリズムをC言語で実装する基本的な手順を以下に示します。

  1. グラフのデータ構造を定義し、頂点数と辺の重み情報を格納します。
#define MAX_VERTEX 100
#define INF 9999

int graph[MAX_VERTEX][MAX_VERTEX];
  1. ベルマンフォード法でグラフの変換を実施する
void bellmanFord(int V, int start)
{
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[start] = 0;

    for (int i = 0; i < V - 1; i++)
    {
        for (int u = 0; u < V; u++)
        {
            for (int v = 0; v < V; v++)
            {
                if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    for (int u = 0; u < V; u++)
    {
        for (int v = 0; v < V; v++)
        {
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v])
                printf("图中存在负权环，无法计算最短路径");
        }
    }

    // 将负权边转换为非负权边
    for (int u = 0; u < V; u++)
    {
        for (int v = 0; v < V; v++)
        {
            if (graph[u][v] != 0)
                graph[u][v] += dist[u] - dist[v];
        }
    }
}
  1. ダイクストラ法を実現して、辺の付け替え後のグラフにおける最短パスを求める
void dijkstra(int V, int start)
{
    int dist[V];
    bool visited[V];

    for (int i = 0; i < V; i++)
    {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;

    for (int count = 0; count < V - 1; count++)
    {
        int u = -1;
        for (int i = 0; i < V; i++)
        {
            if (!visited[i] && (u == -1 || dist[i] < dist[u]))
                u = i;
        }

        visited[u] = true;

        for (int v = 0; v < V; v++)
        {
            if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }

    printf("顶点   最短路径\n");
    for (int i = 0; i < V; i++)
    {
        if (dist[i] == INF)
            printf("%d \t 无限远\n", i);
        else
            printf("%d \t %d\n", i, dist[i]);
    }
}
  1. Johnsonアルゴリズムを実現するために、メイン関数で上記の関数を呼び出します。
int main()
{
    int V;
    int start;
    printf("输入顶点数量：");
    scanf("%d", &V);
    printf("输入起始顶点：");
    scanf("%d", &start);

    printf("输入图的邻接矩阵：\n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            scanf("%d", &graph[i][j]);
        }
    }

    bellmanFord(V, start);
    dijkstra(V, start);

    return 0;
}

上述のコードは ジョンソン の アルゴリズムを実装しています。入力されたグラフの隣接行列から、開始頂点に基いてグラフ内の各頂点までの最短距離を求めます。

bannerAds