Floyd's Algorithm for Shortest Paths(플로이드 알고리즘)

Basic Concept

---

A common problem encountered by air travelers is the determination of the shortest way to fly from one city to another when a direct flight does not exist. Next we develop an algorithm that solves this and similar problems. First, let’s informally review some graph theory.

 

Prerequisite Knowledge: Graph Theory

• vertex, node: 정점
• edge, arc: 이음선
• directed graph, digraph: 방향 그래프
• weight: 가중치
• simple path: 단순경로 (같은 정점을 두 번 지나지 않음)
• path: 경로 (두 정점사이에 edge가 있는 정점들의 나열)
• cycle: 순환 (한 정점에서 다시 그 정점으로 돌아오는 경로)
• cyclic graph: 순환 그래프
• acyclic graph: 비순환 그래프
• weighted graph: 가중치 포함 그래프
• length: 길이
  • (weighted graph) the sum of weights on the path
  • (unweighted graph) the number of edges on the path

 

👉 플로이드 알고리즘은 입·출력값으로 그래프 자료구조를 사용하기 때문에 이에 대한 이해가 필요하다.

 

Weighted Graph

a weighted graph containing n vertices by an array W where

 

$$ \text{W[i][j]} = \begin{cases}_\text{weight on edge} & \text{if there is an edge from $v_i$ to $v_j$}\\ \infty & \text{if there is no edge from $v_i$ to $v_j$} \\ 0 & \text{i = j} \end{cases}$$

 

W represents the graph in the below figure. D contains the lengths of the shortest paths. $D^{(k)}[i][j]$ = length of a shortest path from $v_i$ to $v_j$ using only vertices in the set {$v_1, v_2, ⋯, v_k$} as intermediate vertices.
​

 

👉 그래프 자료구조는 인접행렬로 표현할 수 있다. W는 그래프의 인접행렬을, D는 그래프 상 정점들 간의 최단경로 길이를 나타낸다. 예를 들어 W[i][j]는 정점 $v_{i}$와 $v_{j}$를 연결하는 이음선의 값이다. 

 

 

Floyd’s Algorithm for Shortest Paths using Dynamic Programming

---

Algorithm Design

1. Establish a recursive property (process) with which we can compute $D^{(k)}$ from $D^{(k−1)}$.
2. Solve an instance of the problem in a bottom-up fashion by repeating the process (established in Step 1) for k = 1 to n.

 

$$\begin{align} D^{(k)}[i][j] = minimum(& D^{(k-1)}[i][j], \tag{Case 1}\\ & D^{(k-1)}[i][k] + D^{(k-1)}[k][j]) \tag{Case 2} \end{align}$$

 

Case 1 At least one shortest path from $v_i$ to $v_j$ using only vertices in the set  {$v_1, v_2, \cdots, v_k$} as intermediate vertices, does not use $v_k$.

 

Case 2 All shortest paths from $v_i$ to $v_j$ , using only vertices in the set  {$v_1, v_2, \cdots, v_k$} as intermediate vertices, do use $v_k$.

 

 

👉 $D^{(k)}[i][j]$는 {$v_1, v_2, ⋯, v_k$}의 정점들 만을 통해서 $v_i$ 에서 $v_j$로 가는 최단경로의 길이이다. $D^{(0)}[2][5]$는 중간 정점으로 아무것도 지나지 않고 $v_2$에서 $v_5$로 가는 최단경로의 길이이다. 인접행렬에서 확인할 수 있듯이 그 값은 $\infty$이다. $D^{(1)}[2][5]$는 $v_2$에서 $v_1$을 거쳐 $v_5$로 가 최단경로의 길이를 나타내며 그 값은 14이다.

그래프 상의 어떤 정점도 중간 정점으로 이용하지 않는 $D^{(k)}$은 $W$와 동일하다. 반면 그래프 상의 모든 정점을 중간 정점으로 이용하는 $D^{(n)}$이 구하고자 하는 최종해($D$)이다.
$D^{(0)}$ = $W$, $D^{(n)}$ = $D$

결국 정점들의 개수가 n개 라면 $D^{(0)}, D^{(1)}, ⋯, D^{(n)}$ 값을 계산해 나가고, $D^{(n)} = D$이 구하고자 하는 모든 정점들 사이의 최단 경로가 된다.

 

Pseudo Code

• Floyd's Algorithm for Shortest Paths

void floyd(const size_t n, const graph& g, int** D, int** P);
{
  int i, j, k;
  D = W;

  for(k=1; k <= n; k++)
    for(i=1; i <= n; i++)
      for(j=1; j <= n; j++)
        D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);
}

 

Source Code

• floyd.h

#ifndef FLOYD_H
#define FLOYD_H
#include "graph.h" // Provides graph
using namespace data_structures;

namespace algorithms
{
  void floyd(const int n, const graph g, int** D, int** P);
  // Problem: Compute shortest paths from each vertex in a weighted graph
  // to each of the other vertices. The weights are nonnegative numbers.
  // Inputs: A weighted, directed graph and n, the number of vertices
  // in the graph. The graph is represented by a two-dimensional array
  // edges, which has both its rows and columns indexed from 1 to n,
  // where edges[i][j] is the weight on the edge from the ith vertex
  // to the jth vertex.
  // Outputs: A two-dimensional array d, which has both its rows and
  // columns indexed from 1 to n, where d[i][j] is the length of a
  // shortest path from the ith vertex to the jth vertex.

  void path(int** P, int q, int r);
  // Problem: Print the intermediate vertices on a shortest path from one
  // vertex to another vertex in a weighted graph.
  // Inputs: the array P produced by floyd, and two indices, q and r, of
  // vertices in the graph that is the input to floyd.
  // P[i][j] = highest index of an intermediate vertex on the shortest path
  // from vi to vj, if at least one intermediate vertex exists.
  // 0, if no intermediate vertex exists.
  // Outputs: the intermediate vertex exists.

  void display_graph(const graph g);
  void print_matrix(int** data, const int m, const int n);

  template <typename Item>
  Item** get_matrix_space(const int m, const int n)
  // Postcondition: Return the array containing m*n spaces
  {
    Item** a;
    a = new Item*[m];
    --a; // Offset the pointer to get row index from 1 to m
    for (int i = 1; i <= m; ++i)
    {
      a[i] = new Item[n];
      --a[i];
    }

    // Initialize the matrix
    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        a[i][j] = Item( );

    return a;
  }

  template <typename Item>
  void release_matrix_space(Item** d, int n)
  {
    for (int i = 1; i <= n; ++i)
      delete [ ] (d[i] + 1);
    delete (d+1);
  }
}
#endif

 

• floyd.cpp

// File: floyd.cpp
#include <iostream>
#include <iomanip>
#include "floyd.h"
using namespace std;

namespace algorithms
{
  void floyd(const int n, const graph g, int **D, int **P)
  {
    int i, j, k;

    for (i = 1; i <= g.get_size(); ++i)
      for (j = 1; j <= g.get_size(); ++j)
      {
        D[i][j] = g.get_edge(i, j);
        P[i][j] = 0;
      }

    for (k = 1; k <= n; ++k)
      for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
        {
          if (D[i][k] + D[k][j] < D[i][j])
          {
            P[i][j] = k;
            D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]);
          }
        }
  }

  void path(int **P, int q, int r)
  {
    if (P[q][r] != 0)
    {
      path(P, q, P[q][r]);
      cout << "V" << P[q][r] << " ";
      path(P, P[q][r], r);
    }
  }

  void print_matrix(int** data, const int m, const int n)
  {
    // Print matrix's index
    cout <<"index";
    for (int i = 1; i <= m; ++i)
      cout << setw(7) << i;

    cout << endl << "     ______________________________________________" << endl;

    // Print matrix's data
    for (int i = 1; i <= m; ++i)
    {
      cout << "  " << i <<" |";
      for (int j = 1; j <= n; ++j)
        cout << setw(7) << data[i][j];
      cout << endl;
    }  
    cout << endl;
  }
} // namespace algorithms

 

• floydtest.cpp

// File: floydtest.cpp
#include <iostream>
#include <cstdlib> // Provides EXIT_SUCCESS
#include "graph.h" // Provides graph
#include "floyd.h" // Provides Floyd's algorithm
using namespace std;
using namespace data_structures;
using namespace algorithms;

int main( )
{
  graph exercise(7);
  exercise.set_vertex("V1");
  exercise.set_vertex("V2");
  exercise.set_vertex("V3");
  exercise.set_vertex("V4");
  exercise.set_vertex("V5");
  exercise.set_vertex("V6");
  exercise.set_vertex("V7");
  exercise.set_edge(1, 2, 4);
  exercise.set_edge(1, 6, 10);
  exercise.set_edge(2, 1, 3);
  exercise.set_edge(2, 4, 18);
  exercise.set_edge(3, 2, 6);
  exercise.set_edge(4, 2, 5);
  exercise.set_edge(4, 3, 15);
  exercise.set_edge(4, 5, 2);
  exercise.set_edge(4, 6, 19);
  exercise.set_edge(4, 7, 5);
  exercise.set_edge(5, 4, 1);
  exercise.set_edge(5, 3, 12);
  exercise.set_edge(6, 7, 10);
  exercise.set_edge(7, 4, 8);

  int** distance = get_matrix_space<int>(7, 7);
  int** inter = get_matrix_space<int>(7, 7);

  // Algorithms 3.3 in page 102.
  floyd(exercise.get_size( ), exercise, distance, inter);

  cout << endl
       << "<matrix D - the lengths of the shortest paths>" << endl;
  print_matrix(distance, 7, 7);

  cout << endl
       << "<matrix P - the highest indices of the intermediate vertices"
       << "on the shortest paths>" << endl;
  print_matrix(inter, 7, 7);

  release_matrix_space<int>(distance, 7);
  return EXIT_SUCCESS;
}

 

 

Time Complexity Analysis

---

Basic operation

The instruction in the for-j loop.

 

Input size

n, the number of vertices in the graph. We have a loop within a loop within a loop, with n passes through each loop.

 

Every-Case Time Complexity

$\displaystyle T(n) = n \times n \times n \in \Theta (n^3)$

 

 

Principle of Optimality

---

The Shortest Paths problem is an optimization problem. Therefore, the optimal solution to the instance contains optimal solutions to all subinstances, and the principle of optimality applies.

 

🔗 Dynamic Programming and Optimization Problems(동적계획법과 최적화 문제)

 

👉 최단경로를 구하는 문제는 최적의 원칙이 적용되므로 동적계획법을 사용하여 문제를 해결할 수 있다.

 

 

Exercies

---

Use Floyd’s algorithm for Shortest Paths problem to construct the matrix D, which contains the lengths of the shortest paths, and the matrix P, which contains the highest indices of the intermediate vertices on the shortest paths, for the following graph.

• adjacency matrix for the above graph

/* adjacency matrix for the above graph */
index      1      2      3      4      5      6      7
     __________________________________________________
  1 │      0      4      ∞      ∞      ∞     10      ∞
  2 │      3      0      ∞     18      ∞      ∞      ∞
  3 │      ∞      6      0      ∞      ∞      ∞      ∞
  4 │      ∞      5     15      0      2     19      5
  5 │      ∞      ∞     12      1      0      ∞      ∞
  6 │      ∞      ∞      ∞      ∞      ∞      0     10
  7 │      ∞      ∞      ∞      8      ∞      ∞      0

 

My Answer

• matrices D and P

/* matrix D, which contains the lengths of the shortest paths */
index      1      2      3      4      5      6      7
     __________________________________________________
  1 │      0      4     36     22     24     10     20
  2 │      3      0     32     18     20     13     23
  3 │      9      6      0     24     26     19     29
  4 │      8      5     14      0      2     18      5
  5 │      9      6     12      1      0     19      6
  6 │     26     23     32     18     20      0     10
  7 │     16     13     22      8     10     26      0

/* matrix P, which contains the highest indices of the intermediate
   vertices on the shortest paths */
index      1      2      3      4      5      6      7
     __________________________________________________
  1 │      0      0      5      2      4      0      6
  2 │      0      0      5      0      4      1      4
  3 │      2      0      0      2      4      2      4
  4 │      2      0      5      0      0      2      0
  5 │      4      4      0      0      0      4      4
  6 │      7      7      7      7      7      0      0
  7 │      4      4      5      0      4      4      0