الگوریتم جانسون⚡️توضیح و آموزش الگوریتم جانسون

Q: الگوریتم جانسون چیست؟

الگوریتم جانسون راهی برای یافتن کوتاهترین مسیرها بین تمام جفتهای رئوس در یک گراف جهتدار با یالهای وزندار است. این الگوریتم اجازه میدهد تا برخی از وزنهای یالها اعداد منفی باشند، اما هیچ دور منفی نباید در گراف وجود نداشته باشد.

Q: در الگوریتم جانسون از چه الگوریتمهای دیگری استفاده میشود؟

در الگوریتم جانسون از الگوریتم بلمن-فورد و الگوریتم دایکسترا استفاده میشود.

الگوریتم جانسون

الگوریتم جانسون بر روی گراف‌های جهت دار و وزن دار کار می‌کند، به یال‌ها اجازه می‌دهد وزن‌های منفی داشته باشند اما دور منفی نمی‌تواند وجود داشته باشد زیرا در این صورت هیچ کوتاه‌ترین مسیری برای رئوس قابل دستیابی توسط آن دور وجود نخواهد داشت.

الگوریتم جانسون دارای چهار مرحله اصلی است:

فرض کنید گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... داده شده G باشد. یک راس جدید به اسم S به گراف اضافه کنید، یال‌هایی را از راس جدید به تمام رئوس G اضافه کنید. گراف اصلاح شده را G' در نظر بگیرید.
الگوریتم بلمن-فورد را روی G با شروع S اجرا کنید. فاصله‌های محاسبه شده توسط بلمن-فورد را h[0], h[1], ... , h[V-1] در نظر بگیرید. اگر دور منفی پیدا کردیم، متوقف می‌شویم. توجه داشته باشید که دور منفی را نمی‌توان با راس جدید S ایجاد کرد زیرا یالی به S وجود ندارد. تمام یال‌ها از S هستند.
یال‌های گراف اصلی را دوباره وزن کنید. برای هر یال (u, v)، وزن جدید را (وزن اصلی + h[u] – h[v]) قرار دهید. راس S اضافه شده را بردارید و الگوریتم Dijkstra را برای هر راس اجرا کنید.

در ادامه با یک مثال نحوه کارکرد الگوریتم جانسون را بررسی می‌کنیم.

حتما بخوانید :

معرفی انواع الگوریتم‌ ها

مثال الگوریتم جانسون

گراف زیر را در نظر بگیرید:

راس S را اضافه می‌کنیم و یال‌هایی را از S به تمام رئوس گراف اصلی اضافه می‌کنیم:

ما با استفاده از الگوریتم بلمن-فورد، کوتاه‌ترین فاصله‌ها را از راس S تا تمام رئوس دیگر محاسبه می‌کنیم. کوتاه‌ترین فاصله از S تا رئوس A ،B ،C و D به ترتیب 0، 5-، 1- و 0 است، یعنی h[ ]={0, -5, -1, 0}. هنگامی که این فاصله‌ها را به دست آوردیم، راس S را حذف کرده و با استفاده از فرمول زیر یال‌ها را دوباره وزن می‌کنیم:

w(u, v) = w(u, v) + h[u] – h[v]

نتیجه نهایی گراف با وزن‌های زیر خواهد بود:

از آنجایی که اکنون همه وزن‌ها مثبت هستند، می‌توانیم الگوریتم دایجستراالگوریتم دایجسترا (Dijkstra) از 0 تا 100 - الگوریتم دایکسترااین صفحه الگوریتم دایجسترا (Dijkstra) (یا همان الگوریتم دایکسترا) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم دایجسترا پرداخته است. را برای هر رأس به عنوان راس مبدا اجرا کنیم.

حتما بخوانید :

الگوریتم pso⚡️مزایا و معایب+گام ها و نحوه کار+ پیاده سازی

پیاده‌سازی الگوریتم جانسون

حال که با الگوریتم جانسون آشنا شدیم در ادامه ابتدا به بررسی شبه کد این الگوریتم و سپس به پیاده‌سازی این الگوریتم در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مختلف می‌پردازیم.

شبه کد الگوریتم جانسون

شبه کد زیر، الگوریتم جانسون را در سطح بالایی توصیف می‌کند. زیرروال‌ها توضیح داده نشده‌اند زیرا این الگوریتم‌ها در صفحه بلمن-فورد و صفحه Dijkstra هستند. برای کمک به شما در ارتباط دادن شبه کد به توضیحات الگوریتم، هر یک از مراحل برچسب‌گذاری شده است.

Johnson(G)
    1.
    create G` where G`.V = G.V + {s},
        G`.E = G.E + ((s, u) for u in G.V), and 
        weight(s, u) = 0 for u in G.V
    2.
    if Bellman-Ford(s) == False
        return "The input graph has a negative weight cycle"
    else:
        for vertex v in G`.V:
            h(v) = distance(s, v) computed by Bellman-Ford
        for edge (u, v) in G`.E:
            weight`(u, v) = weight(u, v) + h(u) - h(v)
    3.
        D = new matrix of distances initialized to infinity
        for vertex u in G.V:
            run  (G, weight`, u) to compute distance`(u, v) for all v in G.V
            for each vertex v in G.V:
                D_(u, v) = distance`(u, v) + h(v) - h(u)
        return D

Johnson(G)
    1.
    create G` where G`.V = G.V + {s},
        G`.E = G.E + ((s, u) for u in G.V), and 
        weight(s, u) = 0 for u in G.V
    2.
    if Bellman-Ford(s) == False
        return "The input graph has a negative weight cycle"
    else:
        for vertex v in G`.V:
            h(v) = distance(s, v) computed by Bellman-Ford
        for edge (u, v) in G`.E:
            weight`(u, v) = weight(u, v) + h(u) - h(v)
    3.
        D = new matrix of distances initialized to infinity
        for vertex u in G.V:
            run Dijkstra(G, weight`, u) to compute distance`(u, v) for all v in G.V
            for each vertex v in G.V:
                D_(u, v) = distance`(u, v) + h(v) - h(u)
        return D

Python

# Implementation of Johnson's algorithm in Python3
 
# Import function to initialize the dictionary
from collections import defaultdict
MAX_INT = float('Inf')
 
# Returns the vertex with minimum
# distance from the source
def minDistance(dist, visited):
 
    (minimum, minVertex) = (MAX_INT, 0)
    for vertex in range(len(dist)):
        if minimum > dist[vertex] and visited[vertex] == False:
            (minimum, minVertex) = (dist[vertex], vertex)
 
    return minVertex
 
 
# Dijkstra Algorithm for Modified
# Graph (removing negative weights)
def Dijkstra (graph, modifiedGraph, src):
 
    # Number of vertices in the graph
    num_vertices = len(graph)
 
    # Dictionary to check if given vertex is
    # already included in the shortest path tree
    sptSet = defaultdict(lambda : False)
 
    # Shortest distance of all vertices from the source
    dist = [MAX_INT] * num_vertices
 
    dist[src] = 0
 
    for count in range(num_vertices):
 
        # The current vertex which is at min Distance
        # from the source and not yet included in the
        # shortest path tree
        curVertex = minDistance(dist, sptSet)
        sptSet[curVertex] = True
 
        for vertex in range(num_vertices):
            if ((sptSet[vertex] == False) and
                (dist[vertex] > (dist[curVertex] +
                modifiedGraph[curVertex][vertex])) and
                (graph[curVertex][vertex] != 0)):
                 
                dist[vertex] = (dist[curVertex] +
                                modifiedGraph[curVertex][vertex]);
 
    # Print the Shortest distance from the source
    for vertex in range(num_vertices):
        print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex]))
 
# Function to calculate shortest distances from source
# to all other vertices using Bellman-Ford algorithm
def BellmanFord(edges, graph, num_vertices):
 
    # Add a source s and calculate its min
    # distance from every other node
    dist = [MAX_INT] * (num_vertices + 1)
    dist[num_vertices] = 0
 
    for i in range(num_vertices):
        edges.append([num_vertices, i, 0])
 
    for i in range(num_vertices):
        for (src, des, weight) in edges:
            if((dist[src] != MAX_INT) and
                    (dist[src] + weight < dist[des])):
                dist[des] = dist[src] + weight
 
    # Don't send the value for the source added
    return dist[0:num_vertices]
 
# Function to implement Johnson Algorithm
def JohnsonAlgorithm(graph):
 
    edges = []
 
    # Create a list of edges for Bellman-Ford Algorithm
    for i in range(len(graph)):
        for j in range(len(graph[i])):
 
            if graph[i][j] != 0:
                edges.append([i, j, graph[i][j]])
 
    # Weights used to modify the original weights
    modifyWeights = BellmanFord(edges, graph, len(graph))
 
    modifiedGraph = [[0 for x in range(len(graph))] for y in
                    range(len(graph))]
 
    # Modify the weights to get rid of negative weights
    for i in range(len(graph)):
        for j in range(len(graph[i])):
 
            if graph[i][j] != 0:
                modifiedGraph[i][j] = (graph[i][j] +
                        modifyWeights[i] - modifyWeights[j]);
 
    print ('Modified Graph: ' + str(modifiedGraph))
 
    # Run Dijkstra for every vertex as source one by one
    for src in range(len(graph)):
        print ('\nShortest Distance with vertex ' +
                        str(src) + ' as the source:\n')
        Dijkstra(graph, modifiedGraph, src)
 
# Driver Code
graph = [[0, -5, 2, 3],
        [0, 0, 4, 0],
        [0, 0, 0, 1],
        [0, 0, 0, 0]]
 
JohnsonAlgorithm(graph)

# Implementation of Johnson's algorithm in Python3
 
# Import function to initialize the dictionary
from collections import defaultdict
MAX_INT = float('Inf')
 
# Returns the vertex with minimum
# distance from the source
def minDistance(dist, visited):
 
    (minimum, minVertex) = (MAX_INT, 0)
    for vertex in range(len(dist)):
        if minimum > dist[vertex] and visited[vertex] == False:
            (minimum, minVertex) = (dist[vertex], vertex)
 
    return minVertex
 
 
# Dijkstra Algorithm for Modified
# Graph (removing negative weights)
def Dijkstra (graph, modifiedGraph, src):
 
    # Number of vertices in the graph
    num_vertices = len(graph)
 
    # Dictionary to check if given vertex is
    # already included in the shortest path tree
    sptSet = defaultdict(lambda : False)
 
    # Shortest distance of all vertices from the source
    dist = [MAX_INT] * num_vertices
 
    dist[src] = 0
 
    for count in range(num_vertices):
 
        # The current vertex which is at min Distance
        # from the source and not yet included in the
        # shortest path tree
        curVertex = minDistance(dist, sptSet)
        sptSet[curVertex] = True
 
        for vertex in range(num_vertices):
            if ((sptSet[vertex] == False) and
                (dist[vertex] > (dist[curVertex] +
                modifiedGraph[curVertex][vertex])) and
                (graph[curVertex][vertex] != 0)):
                 
                dist[vertex] = (dist[curVertex] +
                                modifiedGraph[curVertex][vertex]);
 
    # Print the Shortest distance from the source
    for vertex in range(num_vertices):
        print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex]))
 
# Function to calculate shortest distances from source
# to all other vertices using Bellman-Ford algorithm
def BellmanFord(edges, graph, num_vertices):
 
    # Add a source s and calculate its min
    # distance from every other node
    dist = [MAX_INT] * (num_vertices + 1)
    dist[num_vertices] = 0
 
    for i in range(num_vertices):
        edges.append([num_vertices, i, 0])
 
    for i in range(num_vertices):
        for (src, des, weight) in edges:
            if((dist[src] != MAX_INT) and
                    (dist[src] + weight < dist[des])):
                dist[des] = dist[src] + weight
 
    # Don't send the value for the source added
    return dist[0:num_vertices]
 
# Function to implement Johnson Algorithm
def JohnsonAlgorithm(graph):
 
    edges = []
 
    # Create a list of edges for Bellman-Ford Algorithm
    for i in range(len(graph)):
        for j in range(len(graph[i])):
 
            if graph[i][j] != 0:
                edges.append([i, j, graph[i][j]])
 
    # Weights used to modify the original weights
    modifyWeights = BellmanFord(edges, graph, len(graph))
 
    modifiedGraph = [[0 for x in range(len(graph))] for y in
                    range(len(graph))]
 
    # Modify the weights to get rid of negative weights
    for i in range(len(graph)):
        for j in range(len(graph[i])):
 
            if graph[i][j] != 0:
                modifiedGraph[i][j] = (graph[i][j] +
                        modifyWeights[i] - modifyWeights[j]);
 
    print ('Modified Graph: ' + str(modifiedGraph))
 
    # Run Dijkstra for every vertex as source one by one
    for src in range(len(graph)):
        print ('\nShortest Distance with vertex ' +
                        str(src) + ' as the source:\n')
        Dijkstra(graph, modifiedGraph, src)
 
# Driver Code
graph = [[0, -5, 2, 3],
        [0, 0, 4, 0],
        [0, 0, 0, 1],
        [0, 0, 0, 0]]
 
JohnsonAlgorithm(graph)

C++

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
   return (a<b)?a:b;
}
main() {
   int vert, edge, i, j, k, c;
   cout < "Enter no of vertices: ";
   cin > vert;
   cout < "Enter no of edges: ";
   cin > edge;
   cout < "Enter the EDGE Costs:\n";
   for (k = 1; k ≤ edge; k++) { //take the input and store it into adj and cost matrix
      cin > i > j > c;
      adj[i][j] = cost[i][j] = c;
   }
   for (i = 1; i ≤ vert; i++)
      for (j = 1; j ≤ vert; j++) {
         if (adj[i][j] == 0 && i != j)
            adj[i][j] = INF; //if there is no edge, put infinity
      }
   for (k = 1; k ≤ vert; k++)
      for (i = 1; i ≤ vert; i++)
         for (j = 1; j ≤ vert; j++)
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); //find minimum path from i to j through k
   cout << "Resultant adj matrix\n";
   for (i = 1; i ≤ vert; i++) {
      for (j = 1; j ≤ vert; j++) {
            if (adj[i][j] != INF)
               cout < adj[i][j] < " ";
      }
      cout << "\n";
   }
}

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
   return (a < b)?a:b;
}
main() {
   int vert, edge, i, j, k, c;
   cout << "Enter no of vertices: ";
   cin >> vert;
   cout << "Enter no of edges: ";
   cin >> edge;
   cout << "Enter the EDGE Costs:\n";
   for (k = 1; k ≤ edge; k++) { //take the input and store it into adj and cost matrix
      cin >> i >> j >> c;
      adj[i][j] = cost[i][j] = c;
   }
   for (i = 1; i ≤ vert; i++)
      for (j = 1; j ≤ vert; j++) {
         if (adj[i][j] == 0 && i != j)
            adj[i][j] = INF; //if there is no edge, put infinity
      }
   for (k = 1; k ≤ vert; k++)
      for (i = 1; i ≤ vert; i++)
         for (j = 1; j ≤ vert; j++)
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); //find minimum path from i to j through k
   cout << "Resultant adj matrix\n";
   for (i = 1; i ≤ vert; i++) {
      for (j = 1; j ≤ vert; j++) {
            if (adj[i][j] != INF)
               cout << adj[i][j] << " ";
      }
      cout << "\n";
   }
}

JavaScript

// Initialize the dictionary
const MAX_INT = Number.POSITIVE_INFINITY;
 
// Returns the vertex with minimum distance from the source
function minDistance(dist, visited) {
  let minimum = MAX_INT;
  let minVertex = 0;
  for (let vertex = 0; vertex < dist.length; vertex++) {
    if (minimum > dist[vertex] && !visited[vertex]) {
      minimum = dist[vertex];
      minVertex = vertex;
    }
  }
  return minVertex;
}
 
// Dijkstra Algorithm for Modified Graph (removing negative weights)
function Dijkstra(graph, modifiedGraph, src) {
  const numVertices = graph.length;
 
  // Dictionary to check if given vertex
  // is already included in the shortest path tree
  const sptSet = new Array(numVertices).fill(false);
 
  // Shortest distance of all vertices from the source
  const dist = new Array(numVertices).fill(MAX_INT);
  dist[src] = 0;
 
  for (let count = 0; count < numVertices; count++) {
    // The current vertex which is at min Distance
    // from the source and not yet included in the shortest path tree
    const curVertex = minDistance(dist, sptSet);
    sptSet[curVertex] = true;
 
    for (let vertex = 0; vertex < numVertices; vertex++) {
      if (
        !sptSet[vertex] &&
        dist[vertex] > dist[curVertex] + modifiedGraph[curVertex][vertex] &&
        graph[curVertex][vertex] !== 0
      ) {
        dist[vertex] = dist[curVertex] + modifiedGraph[curVertex][vertex];
      }
    }
  }
 
  // Print the Shortest distance from the source
  for (let vertex = 0; vertex < numVertices; vertex++) {
    console.log(`Vertex ${vertex}: ${dist[vertex]}`);
  }
}
 
// Function to calculate shortest distances from source to all other vertices using Bellman-Ford algorithm
function BellmanFord(edges, graph, numVertices) {
  // Add a source s and calculate its min distance from every other node
  const dist = new Array(numVertices + 1).fill(MAX_INT);
  dist[numVertices] = 0;
 
  for (let i = 0; i < numVertices; i++) {
    edges.push([numVertices, i, 0]);
  }
 
  for (let i = 0; i < numVertices; i++) {
    for (const [src, des, weight] of edges) {
      if (dist[src] !== MAX_INT && dist[src] + weight < dist[des]) {
        dist[des] = dist[src] + weight;
      }
    }
  }
 
  // Don't send the value for the source added
  return dist.slice(0, numVertices);
}
 
// Function to implement Johnson Algorithm
function JohnsonAlgorithm(graph) {
  const edges = [];
 
  // Create a list of edges for Bellman-Ford Algorithm
for (let i = 0; i < graph.length; i++) {
for (let j = 0; j < graph[i].length; j++) {
if (graph[i][j] !== 0) {
edges.push([i, j, graph[i][j]]);
}
}
}
 
// Weights used to modify the original weights
const modifyWeights = BellmanFord(edges, graph, graph.length);
 
const modifiedGraph = Array(graph.length).fill().map(() => Array(graph.length).fill(0));
 
// Modify the weights to get rid of negative weights
for (let i = 0; i < graph.length; i++) {
for (let j = 0; j < graph[i].length; j++) {
if (graph[i][j] !== 0) {
modifiedGraph[i][j] = graph[i][j] + modifyWeights[i] - modifyWeights[j];
}
}
}
 
console.log("Modified Graph: " + JSON.stringify(modifiedGraph)+"<br />");
 
// Run Dijkstra for every vertex as source one by one
for (let src = 0; src < graph.length; src++) {
console.log("
"+ "Shortest Distance with vertex " + src + " as the source:"+"
");
Dijkstra(graph, modifiedGraph, src);
}
}
 
// Driver Code
const graph = [[0, -5, 2, 3],
[0, 0, 4, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
 
JohnsonAlgorithm(graph);

// Initialize the dictionary
const MAX_INT = Number.POSITIVE_INFINITY;
 
// Returns the vertex with minimum distance from the source
function minDistance(dist, visited) {
  let minimum = MAX_INT;
  let minVertex = 0;
  for (let vertex = 0; vertex < dist.length; vertex++) {
    if (minimum > dist[vertex] && !visited[vertex]) {
      minimum = dist[vertex];
      minVertex = vertex;
    }
  }
  return minVertex;
}
 
// Dijkstra Algorithm for Modified Graph (removing negative weights)
function Dijkstra(graph, modifiedGraph, src) {
  const numVertices = graph.length;
 
  // Dictionary to check if given vertex
  // is already included in the shortest path tree
  const sptSet = new Array(numVertices).fill(false);
 
  // Shortest distance of all vertices from the source
  const dist = new Array(numVertices).fill(MAX_INT);
  dist[src] = 0;
 
  for (let count = 0; count < numVertices; count++) {
    // The current vertex which is at min Distance
    // from the source and not yet included in the shortest path tree
    const curVertex = minDistance(dist, sptSet);
    sptSet[curVertex] = true;
 
    for (let vertex = 0; vertex < numVertices; vertex++) {
      if (
        !sptSet[vertex] &&
        dist[vertex] > dist[curVertex] + modifiedGraph[curVertex][vertex] &&
        graph[curVertex][vertex] !== 0
      ) {
        dist[vertex] = dist[curVertex] + modifiedGraph[curVertex][vertex];
      }
    }
  }
 
  // Print the Shortest distance from the source
  for (let vertex = 0; vertex < numVertices; vertex++) {
    console.log(`Vertex ${vertex}: ${dist[vertex]}`);
  }
}
 
// Function to calculate shortest distances from source to all other vertices using Bellman-Ford algorithm
function BellmanFord(edges, graph, numVertices) {
  // Add a source s and calculate its min distance from every other node
  const dist = new Array(numVertices + 1).fill(MAX_INT);
  dist[numVertices] = 0;
 
  for (let i = 0; i < numVertices; i++) {
    edges.push([numVertices, i, 0]);
  }
 
  for (let i = 0; i < numVertices; i++) {
    for (const [src, des, weight] of edges) {
      if (dist[src] !== MAX_INT && dist[src] + weight < dist[des]) {
        dist[des] = dist[src] + weight;
      }
    }
  }
 
  // Don't send the value for the source added
  return dist.slice(0, numVertices);
}
 
// Function to implement Johnson Algorithm
function JohnsonAlgorithm(graph) {
  const edges = [];
 
  // Create a list of edges for Bellman-Ford Algorithm
for (let i = 0; i < graph.length; i++) {
for (let j = 0; j < graph[i].length; j++) {
if (graph[i][j] !== 0) {
edges.push([i, j, graph[i][j]]);
}
}
}
 
// Weights used to modify the original weights
const modifyWeights = BellmanFord(edges, graph, graph.length);
 
const modifiedGraph = Array(graph.length).fill().map(() => Array(graph.length).fill(0));
 
// Modify the weights to get rid of negative weights
for (let i = 0; i < graph.length; i++) {
for (let j = 0; j < graph[i].length; j++) {
if (graph[i][j] !== 0) {
modifiedGraph[i][j] = graph[i][j] + modifyWeights[i] - modifyWeights[j];
}
}
}
 
console.log("Modified Graph: " + JSON.stringify(modifiedGraph)+"<br />");
 
// Run Dijkstra for every vertex as source one by one
for (let src = 0; src < graph.length; src++) {
console.log("
"+ "Shortest Distance with vertex " + src + " as the source:"+"
");
Dijkstra(graph, modifiedGraph, src);
}
}
 
// Driver Code
const graph = [[0, -5, 2, 3],
[0, 0, 4, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
 
JohnsonAlgorithm(graph);

پیچیدگی زمانی الگوریتم جانسون

مراحل اصلی در الگوریتم جانسون عبارتند از الگوریتم بلمن-فورد که یک بار و دایکسترا که V بار فراخوانی می‌شود. پیچیدگی زمانی بلمن فورد O(VE) و پیچیدگی زمانی دایکسترا O(VLogV) است بنابراین پیچیدگی زمانی کلی الگوریتم جانسون O(V2log V + VE) است.

حتما بخوانید :

الگوریتم پریم (Prim) چیست ⚡️مثال+پیاده سازی+پیچیدگی زمانی

کاربردهای الگوریتم جانسون

کاربردهای مختلفی برای الگوریتم جانسون وجود دارد که برخی از آنها به شرح زیر است:

پرکاربردترین کاربرد الگوریتم جانسون، شبکه‌بندی جاده‌ها است.
برای مسیریابی شبکه برای انتخاب مسیر بهینه برای ارسال بسته‌های داده استفاده می‌شود.
همچنین در GPS برای یافتن بهترین مسیر با کوتاه‌ترین مسیر و کم‌ترین تراکم ترافیک استفاده می‌شود.
این الگوریتم به‌طور گسترده‌ای برای اهداف لجستیک توسط شرکت‌های مختلف استفاده می‌شود تا هزینه حمل و نقل آنها به حداقل برسد.

جمع‌بندی

در این مقاله با الگوریتم جانسون آشنا شدیم. ما همچنین در مورد عملکرد الگوریتم جانسون آموختیم و دیدیم که چگونه الگوریتم جانسون از الگوریتم دایکسترا و الگوریتم بلمن فورد برای افزایش کارایی الگوریتم جانسون استفاده می‌کند، همینطور یاد گرفتیم که چگونه الگوریتم جانسون را پیاده‌سازی کنیم؛ همچنین پیچیدگی زمانی این الگوریتم را تحلیل کردیم و با کاربردهای آن در دنیای واقعی آشنا شدیم.

الگوریتم جانسون چیست؟

الگوریتم جانسون راهی برای یافتن کوتاه‌ترین مسیرها بین تمام جفت‌های رئوس در یک گراف جهت‌دار با یال‌های وزن‌دار است. این الگوریتم اجازه می‌دهد تا برخی از وزن‌های یال‌ها اعداد منفی باشند، اما هیچ دور منفی نباید در گراف وجود نداشته باشد.