C 语言 Johnson 算法

2025 年 1 月 7 日 | 阅读 22 分钟

图论和计算机科学的领域浩瀚而复杂，算法在处理复杂挑战方面至关重要。其中一个问题是所有顶点对之间的最短路径问题，其定义是计算加权有向图中所有顶点对之间的最短路径。从网络路由到地理测绘，从社交网络研究到其他研究领域，这个问题都至关重要。尽管存在几种解决此问题的方法，但 Johnson 算法在构建稀疏网络和使用包含负权重的图时，效果相对较好。

为了分析算法在图中的作用，以下内容确定了算法的价值

现实世界中普遍存在的互联系统可以通过图来很好地建模，图可以描述大多数系统。图在许多学科领域中用于建模结构和分析结构，例如社交网络；其中，人是节点，他们之间的连接是边；在交通系统中，城市是节点，它们之间的公路是边。在各种应用中，识别这些图中的最短路径至关重要，主要是为了提高效率、降低成本和优化路线。

就难度而言，最短路径问题定义为所有顶点对的最短路径问题。因此，所有顶点对最短路径问题旨在找到图中每个顶点到其他每个顶点的最短路径。随着图的扩展，此问题的计算难度也会增加。对于大型图，像 Floyd-Warshall 这样需要 O(V3) 时间的方法可能太慢。因此，需要更好的算法，特别是对于稀疏图，例如边数 (E) 远小于顶点数 (V) 的图。

Johnson 算法

上述需求表明需要一种可适应的方法来培训前往欧洲学术机构的未来图书管理员。Donald B. Johnson 于 1977 年引入了 Johnson 算法，以改进所有顶点对最短路径问题的可靠性。如果不存在负权环，则该算法可用于稀疏图，并支持边具有正权和负权。它结合了 Bellman-Ford 算法和 Dijkstra 算法这两种著名的算法。

重构图的权重：Johnson 方法的第一步是为了确保所有边权重都是非负的，重构图是 Johnson 方法的第一道工序。使用 Bellman-Ford 方法，该方法能够处理包含负权重的图并识别负权环。该方法通过使用潜在函数的修改来实现，即添加一个新节点，该节点与每个现有节点都通过权重为零的边相连，然后使用 Bellman-Ford。
应用 Dijkstra 算法：上述 Johnson 算法的工作原理如下：它首先重构图的权重，然后应用上述已发现的 Dijkstra 算法来找出每个顶点到其他每个顶点的最短路径。实际上，Dijkstra 技术使用链接优先队列，其运行时间为 O(VlogV+E)，非常适合仅包含非负权重的各种网络。
调整权重：Johnson 的方法会根据重构图上找到的最短路径的原始权重来调整距离。此阶段可确保原始图形问题中的最优路径是正确的。

最短路径问题——所有顶点对，尤其是在节点众多且边权重复杂的情况下，是一个挑战。

所有顶点对最短路径 (APSP) 作为图论中的一个基本问题，在不同领域也有广泛的应用。然而，随着图的大小和复杂结构的增加，该问题变得极具挑战性。以下内容阐述了与 APSP 问题相关的关键障碍：

1. 计算复杂度

高时间复杂度：APSP 问题类似于最短路径问题，需要计算图中每对顶点之间的最短路径。顶点对的数量为 V2，这导致处理需求的急剧增长。如今的网络规模使得 Floyd-Warshall 算法等具有 O(V3) 时间复杂度的技术变得不可行。
图的大小：由于图中顶点和边的数量，计算图中每个顶点到其他每个顶点的所有最短路径在计算上非常密集。在顶点和网络边缘数量可能达到数百万的应用中，如社交网络分析、物流和电信等领域，这个问题尤为突出。
内存使用：正如 APSP 问题一样，存储所有最短路径对也需要消耗大量内存。对于具有 V 个顶点的网络，存储最短路径矩阵需要 O(V2) 的空间。对于非常大的图，这可能超过可用 RAM 的容量，从而导致更多实现问题。

2. 处理反向权重

负边权重：在许多实际应用场景中，图的边可能具有负权重。在成本或数量驱动的方法中，负权重可能代表诸如成本降低、退款或其他经济或物流模型中的奖励等现象。另一方面，负权重实际上给最短路径计算带来了困难，因为它们可能产生错误或不准确的结果。
负权环：当图中存在负权环时，难度会更大。这些是边权重总和为负的环，如果沿着它们前进，会得到一个路径长度不断减小的迭代路径。它们在心理上与负权重和负权环有关，或者路径权重低于零；不幸的是，Dijkstra 算法无法处理负权重。
算法限制：这包括 A*，它需要与起点不同的距离，以及在负权重图中的每个顶点都与几种最短路径方法的设计不兼容。例如，一种著名的非负权重网络算法——Dijkstra 算法——在处理负权重的网络时会失败。因此，研究人员在应对 APSP 问题时面临的首要挑战是制定一种能够有效高效地处理负权重的有价值的算法。

3. 图的密度

更具体地说，可以通过书中各章节介绍的图概念和方面对图的稀疏性和密度产生影响来判断其主题内和各章节之间的连贯性。

密集网络：在连接网络中，计算负载会显着增加，其中边的特定密度达到网络中可能存在的最大值，即 E≈V2。在这种情况下，必须处理许多边才能得到答案，这使得在时间和空间方面解决 APSP 问题变得复杂。
稀疏图：当边数 E 小于顶点数 V 的平方时，即 E≥V2，这会带来一套不同的问题。尽管较少的边可能导致更快的计算，但这同样意味着标准密集图方法不能有效地用于执行算法。在这种情况下，APSP 问题的解决方案必须基于特定的启发式方法，而这些方法源于图很可能是稀疏的这一事实。

4. 算法均衡

时间与空间权衡：值得注意的是，大多数处理 APSP 问题的算法在时间和空间复杂度上都涉及权衡。例如，某些算法可能比其他算法更快——但更快的算法在计算的某个阶段可能需要更多的内存来存储结果，而较慢的版本可能只需要更长的计算时间。几乎无法协商这些权衡，尤其是在处理内存和时间受限的大型图时。
精度与复杂度：为了降低计算的复杂性，问题有时可以近似解决。然而，这样做会导致准确性和时间之间的折衷。在当前情况下，缺点是近似算法虽然能更快地解决 APSP 问题，但可能无法始终指出精确的最短路径。

5. 可扩展性问题

随图大小缩放：解决 APSP 问题所需的计算需求随图大小呈指数级增长。在较小邻域图中表现良好的算法，在图大小增加时可能表现不佳，从而导致性能缺陷。在现代应用中，网络可能非常大，例如在 SNP 或大规模优化的情况下，这更具挑战性。
分布式计算挑战：为了避免可扩展性问题，分布式计算最常见的应用之一是将最短路径的计算负载分布到多个处理器或计算机上。然而，这也会带来新的问题，例如协调分散的组件、处理通信成本以及确保计算路径的正确性和一致性。

6. 实时处理要求

动态图：许多应用图是动态的；也就是说，它们是逐渐形成的。顶点和边可能与灵活性相关；也就是说，顶点和边可以每天添加甚至删除。当应用于动态图时，查找 APSP 的问题尤其变得更加困难，因为路径必须随着图的变化而实时更新。因此，需要有算法能够以不需要重新计算的方式来处理动态更新。
实时约束：在某些应用中，例如在线导航系统、网络路由等，必须实时确定最短路径。由于 APSP 问题的解决方案需要在合理的时间内获得，因此我们将效率与时间联系起来。考虑到负权重或随时间的变化等因素，在这些图中实现这一点或维持准确性和复杂性并不容易。

7. 特定应用的难题

不同的权重指标：具体来说，根据给定的应用，边权重可能表示时间、成本、距离，也可能表示其他变量或两个或多个变量的组合。由于存在多种权重指标，APSP 问题变得更具挑战性，因为算法必须足够通用，能够处理许多情况并准确反映计算最短路径时的相关指标。
与其他算法的集成：在实际情况中，解决 APSP 问题可能需要将问题的制定包含其他优化过程或步骤。例如，在物流领域，APSP 解决方案可以成为更全面的优化问题的一部分，例如在计划、资源分配或其他约束中。当然，当需要保证一个愉快的组合，同时保持计算的复杂性和精确性时，还需要考虑其他因素。

8. 处理异构图

处理具有各种权重类型的异构图：边也可以关联不同类型的权重：时间、成本、距离等。与传统的同构网络相反，需要进行多目标优化来解决 APSP 问题，并从这些权重中识别最短路径。这使得问题更加复杂，因为人们被迫权衡实现一个目标对实现其他目标机会的影响。

表示和处理异构图的困难：处理组合类型和规模的数据在表示和处理异构图时具有挑战性。为了能够提供准确且相关的最短路径结果，算法必须处理这种异构性。

由于计算复杂度、处理负权重的需求、图密度变化以及时间和空间平衡的需求，所有顶点对最短路径是一个复杂的问题。但该主题远未枯竭，因为还存在关于规模、实时性能和各种应用需求的问题。这些问题需要复杂的算法，这些算法提供合理的准确性和效率，并且可以轻松地适应各种情况，例如 Johnson 算法。鉴于图在各个领域的密度和规模不断增加，APSP 问题是计算机科学和其他学科中一个重要且活跃的研究和实践领域。

C 语言实现

下面是 Johnson 算法的 C 语言实现。此实现假设图使用邻接表表示。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Define the structure for the edges
struct Edge {
    int src, dest, weight;
};

// Define the structure for the graph
struct Graph {
    int V, E;
    struct Edge* edge;
};

// Utility function to create a new graph
struct Graph* create graph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(graph->E * sizeof(struct Edge));
    return graph;
}

// Utility function to print the solution
void print solution(int dist[], int n) {
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Bellman-Ford algorithm to find shortest paths from source
int BellmanFord(struct Graph* graph, int src, int dist[]) {
    int V = graph->V;
    int E = graph->E;

    // Step 1: Initialize distances from src to all other vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // Step 3: Check for negative-weight cycles
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            return 0; // Negative cycle detected
    }

    return 1;
}

// Utility function to find the vertex with a minimum distance value
int minDistance(int dist[], int sptSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// Dijkstra’s algorithm to find shortest paths from src
void Dijkstra(int V, int graph[V][V], int src, int dist[]) {
    int sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet, V);
        sptSet[u] = 1;

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

// Johnson’s algorithm to find all pairs shortest paths
void Johnson(struct Graph* graph) {
    int V = graph->V;
    int E = graph->E;
    int newV = V + 1;
    struct Graph* newGraph = createGraph(newV, E + V);

    for (int i = 0; i < E; i++) {
        newGraph->edge[i].src = graph->edge[i].src;
        newGraph->edge[i].dest = graph->edge[i].dest;
        newGraph->edge[i].weight = graph->edge[i].weight;
    }

    for (int i = 0; i < V; i++) {
        newGraph->edge[E + i].src = newV - 1;
        newGraph->edge[E + i].dest = i;
        newGraph->edge[E + i].weight = 0;
    }

    int h[newV];
    if (!BellmanFord(newGraph, newV - 1, h)) {
        printf("Graph contains negative weight cycle\n");
        return;
    }

    int reweightedGraph[V][V];
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            reweightedGraph[u][v] = INT_MAX;
        }
    }

    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        reweightedGraph[u][v] = graph->edge[i].weight + h[u] - h[v];
    }

    for (int u = 0; u < V; u++) {
        int dist[V];
        Dijkstra(V, reweightedGraph, u, dist);
        for (int v = 0; v < V; v++) {
            if (dist[v] != INT_MAX) {
                dist[v] = dist[v] + h[v] - h[u];
            }
            printf("Shortest distance from %d to %d is %d\n", u, v, dist[v]);
        }
    }

    free(newGraph->edge);
    free(newGraph);
}

int main() {
    int V = 5;
    int E = 8;
    struct Graph* graph = createGraph(V, E);

    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    Johnson(graph);

    free(graph->edge);
    free(graph);

    return 0;
}

输出

Shortest distance from 0 to 0 is 0
The shortest distance from 0 to 1 is -1
The shortest distance from 0 to 2 is 2
The shortest distance from 0 to 3 is 2147483646
The shortest distance from 0 to 4 is -2147483647
The shortest distance from 1 to 0 is -2147483646
Shortest distance from 1 to 1 is 0
Shortest distance from 1 to 2 is 3
Shortest distance from 1 to 3 is 2147483647
The shortest distance from 1 to 4 is -2147483646
Shortest distance from 2 to 0 is 2147483647
Shortest distance from 2 to 1 is 2147483647
Shortest distance from 2 to 2 is 0
Shortest distance from 2 to 3 is 2147483647
Shortest distance from 2 to 4 is 2147483647
The shortest distance from 3 to 0 is -2147483644
The shortest distance from 3 to 1 is -2147483646
Shortest distance from 3 to 2 is 5
Shortest distance from 3 to 3 is 0
The shortest distance from 3 to 4 is -2147483644
Shortest distance from 4 to 0 is 2147483647
Shortest distance from 4 to 1 is 2147483647
Shortest distance from 4 to 2 is 2147483647
Shortest distance from 4 to 3 is 2147483647
Shortest ... ( text has been truncated )

Johnson 算法的优势

Johnson 技术，尤其是在加权有向图的背景下寻找所有顶点对最短路径 (APSP) 的问题方面，无疑是图论领域的一项重要贡献。当然，必须强调专业教师选择该算法是基于其效率、灵活性以及处理可能对其他算法致命的关键场景的能力。在下一节中，我们将探讨确保 Johnson 方法被选为解决许多应用中 APSP 问题的最有效方法的一些优势。

在紧凑图中的有效性
Johnson 算法的主要优点之一是它在稀疏图的情况下带来了高效的性能。如果边数 (E) 很少，并且远小于顶点数平方，则该图称为稀疏图。在社交网络、交通和通信等许多应用中，图通常是稀疏的。因此，优化处理这些图的过程至关重要。
这正是 Johnson 方法发挥作用的场合。该算法的时间复杂度为 O(V2 logV+VE)，远优于经典的 Floyd-Warshall 算法 O(V3) 来解决 APSP 问题。这是因为该技术利用了 Dijkstra 算法，该算法在稀疏网络中进行最短路径计算时特别有效。Johnson 方法通过 Bellman-Ford 方法的初步重构权重应用，从而增强了 Dijkstra 算法的效率，快速返回所有顶点对的最短路径。
处理反向权重
Johnson 技术的优点是它也可以应用于包含负边权重的任何平面图。值得承认的是，负权重在现实生活过程中相当频繁地出现；与这些模式相关的场景可以是成本敏感应用中的损失、折扣或激励。然而，负权重本质上对最短路径算法提出了挑战，因为使用负权重会得到错误的结果，或者更糟的是，负权环会中断算法的运行。
Johnson 技术中的重构操作巧妙地解决了这个问题。Bellman-Ford 的松弛通过添加一个与所有其他顶点连接权重为零的新顶点来计算一个潜在函数，该函数重新分配了倒数边的概率。然后从这个新顶点执行该过程。这个新顶点代表了从集合 S 中的任意顶点到集合 T 中的顶点的函数应用结果。这种重构对于确保 Dijkstra 方法在最短路径计算中的应用安全至关重要，因为它确保了所有边权重都是非负的。重构图中的最短路径实际上就是原始图中的最短路径，因为重要的是要注意重构也保持了顶点之间的距离。
此外，Johnson 算法的 Bellman-Ford 步骤改善了图的重构，并且还检测到了负权环。这意味着如果图中存在此类环，则过程将提前终止，得出给定图的 APSP 问题无法解决。算法通常珍视这种额外的鲁棒性，因为它有助于提高在困难情况下的可靠性。
适应性和广泛性
然而，Johnson 方法的灵活性使其有可能应用于不同类型的网络和各种问题。这种优势在于选择 Dijkstra 和 Bellman-Ford 算法的方面，并将它们组合成一个算法，该算法能够解决单凭其中任何一种方法都无法解决的图类问题。
例如，Dijkstra 在图中有负系数时性能会很差，尽管它在包含非负系数的网络中非常高效。另一方面，尽管 Bellman-Ford 算法能够处理负权重，但其 O(VE) 的时间复杂度使其不太适合大型网络。在实际计算最短路径时，使用 Dijkstra 算法，而使用 Bellman-Ford 进行重构。因此，Johnson 的程序巧妙地结合了两者。由于这种组合，Johnson 方法优于其他方法，因为它效率高，并且适用于多种图，无论这些图是否包含负权重。
同时，在技术构建中使用的形容词捕捉了其跨领域的通用性。无论如何，Johnson 方法根据特定图的细节，提供了一种强大而简洁的方法来解决 APSP 问题，用于处理交通网络、通信或社交网络。
可扩展性
虽然结果基于小型图，但在实践中通常会遇到大型图，尤其是在现实场景中——因此，可扩展性必然成为一个问题。Johnson 技术的特点是优化了时间复杂度，这使其能够解决大规模问题，尤其是在稀疏网络中。其他 APSP 技术，如 Floyd-Warshall，在 O(V3) 时更慢，当顶点数量很大时，成本会很高。因此，该算法在 O(V2 logV + VE) 下更快，并且在图大小增加时更优。
在网络路由等应用中，网络图可能包含数百万个节点和边，这种可扩展性至关重要。Johnson 技术即使在问题规模增加时也是一种可行的解决方案，因为它能够有效地处理如此庞大的网络。
实际应用
Johnson 方法的最后一个优点是其实用性，这意味着实际可行性。对于许多现实世界的问题，需要精确可靠地解决 APSP 问题。因此，需要高效的解决方案。Johnson 算法满足了这些要求，它提供了实际且理论上可行的解决方案。
例如，在网络路由中，算法高效地计算最短路径，可以随着路由表的更新而立即更新，从而提高效率。这样，通过采用该算法，可以节省时间和金钱来优化大型复杂交通网络。Joshua 通过使用 Johnson 方法积累了关于大型社交网络成员互连的信息；此方法可用于 SNA 来识别两个大型网络之间的短连接，从而揭示社交互动和后果的细节。
该算法处理负权重的稳定性也可能提高其适用性，因为它可以在不需要大量调整或处理特殊情况的情况下用于解决其他问题。
理论构建
该方法将处理社交媒体的方法与务实的实施愿景相结合，并将可靠性和稳定性指定为理论构建。
Johnson 的方法在实践中是适用的，同时在理论层面上也是经过深思熟虑的。Johnson 对 Bellman-Ford 和 Dijkstra 算法的修改反映了他对经典算法的优势和劣势的深刻理解。Johnson 算法正是通过弥补一种算法的不足并利用另一种算法的优势，提供了一种强大而有用的解决方案。
然而，Johnson 的方法在图算法解决 APSP 问题方面具有重要意义，因为它在许多情况下都非常有效，并且具有复杂的公式和方法的理论稳定性。
Johnson 有几个优点，这就是为什么该方法在解决有向加权图中的所有顶点对最短路径问题方面真正有价值。在所有图算法中，它以其实用性、可扩展性、灵活性、在稀疏图中的速度以及对负权重的适用性而著称。无论如何，无论是理论分析还是实际应用，Johnson 的方法都代表了一种强大而稳定的解决图论中最基本问题之一的方法。该组件在各种环境中的使用及其持续的相对受欢迎程度可以解释其在学术界和现实世界中的适用性。

应用 Johnson 算法

Johnson 方法是一种多功能且高效地提供所有顶点对最短路径问题的相关解决方案的算法，因此可用于不同领域。前者已被证明在稀疏图中非常有效，而后者能够处理具有正边权重和负边权重的图，因此适用于许多实际情况。下面解释 Johnson 算法的一些应用，我们看看该算法如何处理网络路由、地理信息系统、社交网络分析等领域的难题。

网络路由
在通信网络领域，确定最合适的数据传输通道通常被认为是一个非常重要的角色。服务器、交换机和路由器是节点侧，连接它们的线路称为边。通常，边的权重值代表传输成本，该成本可能受拥塞、延迟或带宽的影响。不允许数据包在旅途中花费时间有助于最大限度地减少延迟，从而提高网络性能。
可以应用 Johnson 技术来减少网络中路由表的负载。数据包由包含网络中任意两个节点之间最短路径性质的路由表控制。由于通信网络中节点集可能很大，但节点之间的连接很少，因此 Johnson 方法在最有效地确定这些最短路径方面非常有效。
Johnson 的方法也适用于通信网络中部分或全部连接的权重为负值的情况。虽然这些权重可能表示实际的激励、成本节省或优先级路由，但这些阻碍性的负权重肯定会使路由过程复杂化。由于 Johnson 可以保证我们保持路由成本最优化以避免进入负权环，因此 Johnson 算法会重构所有负权重，然后应用 Dijkstra 算法。
地理信息系统
如今，GIS，即地理信息系统，在犯罪制图中得到了广泛应用。
GIS 的主要组成部分包括通过地图绘制和图算法（也涉及物流和路由）来组织和分析空间数据。例如，在交通网络中，道路和公路由边表示，而城市和十字路口构成节点。任何边的权重可能指通行费、燃料消耗、距离或覆盖距离所需的时间。
Johnson 技术在路线导航、配送资源选择和应对灾难等应用中非常有用，因为它可以帮助确定交通网络内多个地点之间的最短连接。因此，物流组织会获得明显的好处，包括减少旅行时间或距离，从而直接降低成本并改善服务交付。值得注意的是，有一个名为 Johnson 的算法可以应用于定义配送服务的最佳路线，当它必须到达多个地点并确保准时以最佳成本价格交付时。
此外，GIS 通常处理庞大而复杂的网络，这意味着从一个点到另一个点可能有数千种方式。然而，当图 G 是稀疏的时，这在使用社交网络等海量数据时很常见，Johnson 算法在处理这些稀疏图方面具有额外的优势。然而，该技术在提供最短路径方面非常快速，即使存在大量所有顶点对最短路径的运输网络，无论网络规模如何。
社交网络分析
另一种大家熟悉的技巧是 Johnson 技巧，在社交网络中，人或其他事物被描绘成节点，互动被描绘成边。理解社交网络中两个人之间的最短路径可以揭示很多关于社交互动以及信息或行动流动的信息。
例如，在社交网络分析中，尽管分隔度定义了两个人之间的步数，但包含该步数的路径可以显示出在两个人之间交换信息所需的所有连接。它经常被用来识别关键意见领袖——那些能够快速在网络中传播信息的人。在庞大的人群中，Johnson 算法可以快速提供最短路径，因此学者可以分析甚至可视化网络的组织结构。
同样，社交网络在某些情况下可能不利，例如人际冲突或敌意。在找到最短路径之前，Johnson 算法可以通过规范化网络来处理这种情况，使所有边权重都为正。这种重构使得对网络动态有更全面的了解，因为它不仅考虑了正向互动。

下一个主题kosarajus-algorithm-in-c

← 上一个下一个 →

C 语言 Johnson 算法