{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e02cd782",
   "metadata": {},
   "source": [
    "# Практика №2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48a6e585",
   "metadata": {},
   "source": [
    "## Операции над множествами. Свойства бинарных отношений. Замыкания отношений\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ae75977",
   "metadata": {},
   "source": [
    "Множества являются неопределяемыми понятиями и представляют собой неупорядоченную коллекцию уникальных элементов.\n",
    "То есть, что два множества совпадают, если содержат одинаковые элементы.\n",
    "Множества, состоящие из конечного числа элементов, называются конечными, в противном случае множества являются бесконечными. Конечное множество можно задать перечислением его элементов. Рассмотрим как можно работать с множествами средствами языка Python на примере конечных множеств.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca4afee1",
   "metadata": {},
   "source": [
    "### Способы задания множеств\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d848525f",
   "metadata": {},
   "source": [
    "перечисление элементов множества в фигурных скобках:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "569b7ff7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'orange', 'apple', 'banana'}\n",
      "<class 'set'>\n"
     ]
    }
   ],
   "source": [
    "fruits = {\"banana\", \"apple\", \"orange\"}\n",
    "print(fruits)\n",
    "print(type(fruits))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3e9458e",
   "metadata": {},
   "source": [
    "Единственное ограничение, что таким образом нельзя создать пустое множество. Вместо этого будет создан пустой словарь:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d446184f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'dict'>\n"
     ]
    }
   ],
   "source": [
    "wrong_empty_set = {}\n",
    "print(type(wrong_empty_set))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60a0a658",
   "metadata": {},
   "source": [
    "Для создания пустого множества нужно непосредственно использовать set():\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3b7ce4b6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'set'>\n"
     ]
    }
   ],
   "source": [
    "correct_empty_set = set()\n",
    "print(type(correct_empty_set))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47b6bfac",
   "metadata": {},
   "source": [
    "Множество можно задать с помощью set(), если передать в нее какой-либо объект, по которому можно проитерироваться\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6d41db64",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'orange', 'apple', 'banana'}\n",
      "<class 'set'>\n"
     ]
    }
   ],
   "source": [
    "fruits_set = set({\"banana\", \"apple\", \"banana\", \"orange\"})\n",
    "print(fruits_set)\n",
    "print(type(fruits_set))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "99b8c1ea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "fruits_set_1 = set({\"apple\", \"orange\", \"banana\", })\n",
    "print(fruits_set == fruits_set_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b420cc2",
   "metadata": {},
   "source": [
    "### Подмножество и надмножество\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "98eb8ea5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Подмножество!\n",
      "Надмножество!\n"
     ]
    }
   ],
   "source": [
    "# Множество чисел Фибоначчи меньших 100\n",
    "fibonacci_numbers = {0, 1, 2, 3, 34, 5, 8, 13, 21, 55, 89}\n",
    "\n",
    "# Множество натуральных чисел меньших 100\n",
    "natural_numbers = set(range(100))\n",
    "\n",
    "# Множество чисел Фибоначчи является подмножеством множества\n",
    "# натуральных чисел\n",
    "if fibonacci_numbers.issubset(natural_numbers):\n",
    "    print(\"Подмножество!\")\n",
    "\n",
    "# В свою очередь множество натуральных чисел является\n",
    "# надмножеством множества чисел Фибоначчи\n",
    "if natural_numbers.issuperset(fibonacci_numbers):\n",
    "    print(\"Надмножество!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c861227",
   "metadata": {},
   "source": [
    "Пустое множество является подмножеством абсолютно любого множества.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2946f658",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "empty = set()\n",
    "\n",
    "# Методы issubset и issuperset могут принимать любой iterable-объект\n",
    "print(\n",
    "    empty.issubset(range(100))\n",
    "    and empty.issubset([\"red\", \"green\", \"blue\"])\n",
    "    and empty.issubset(set())\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb5a7764",
   "metadata": {},
   "source": [
    "Само множество является подмножеством самого себя.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "019bb3ac",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Подмножество!\n"
     ]
    }
   ],
   "source": [
    "natural_numbers = set(range(100))\n",
    "\n",
    "if natural_numbers.issubset(natural_numbers):\n",
    "    print(\"Подмножество!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "effdf363",
   "metadata": {},
   "source": [
    "### Операции над множествами\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bc824be",
   "metadata": {},
   "source": [
    "Объединение множеств\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ce1f88c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'orange', 'pear', 'banana', 'apple'}\n"
     ]
    }
   ],
   "source": [
    "my_fruits = {\"apple\", \"orange\"}\n",
    "your_fruits = {\"orange\", \"banana\", \"pear\"}\n",
    "\n",
    "# Для объединения множеств (типа set) можно использовать оператор `|`,\n",
    "\n",
    "our_fruits = my_fruits | your_fruits\n",
    "print(our_fruits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "36e34918",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'orange', 'pear', 'apple', 'banana'}\n"
     ]
    }
   ],
   "source": [
    "# Также можно использовать ментод union.\n",
    "# Отличие состоит в том, что метод union принимает не только\n",
    "# объект типа set, а любой iterable-объект\n",
    "you_fruit_list: list = list(your_fruits)\n",
    "our_fruits: set = my_fruits.union(you_fruit_list)\n",
    "print(our_fruits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edb92d2a",
   "metadata": {},
   "source": [
    "Добавление элементов в множество.\n",
    "Добавление элементов в множество можно рассматривать как частный случай объединения множеств за тем исключением, что добавление элементов изменяет исходное множество, а не создает новый объект\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "af8a9b6a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'red', 'purple', 'green', 'blue'}\n"
     ]
    }
   ],
   "source": [
    "colors = {\"red\", \"green\", \"blue\"}\n",
    "\n",
    "# Метод add добаляет новый элемент в множество\n",
    "colors.add(\"purple\")\n",
    "# Добавление элемента, который уже есть в множестве, не изменяет\n",
    "# это множество\n",
    "colors.add(\"red\")\n",
    "print(colors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "103d30b9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 9}\n"
     ]
    }
   ],
   "source": [
    "# Метод update принимает iterable-объект (список, словарь, генератор и т.п.)\n",
    "# и добавляет все элементы в множество\n",
    "numbers = {1, 2, 3}\n",
    "numbers.update(i**2 for i in [1, 2, 3])\n",
    "print(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "765338fd",
   "metadata": {},
   "source": [
    "### Свойства множеств\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cb16831",
   "metadata": {},
   "source": [
    "К основным свойствам множеств, которые мы хотим проверять, относятся рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность.\n",
    "Сгенерируем произвольное бинарное отношение\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fac374b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "x = 4\n",
    "y = 4\n",
    "array = [[random.randint(0, 1) for _ in range(x)] for _ in range(y)]\n",
    "array"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71d50746",
   "metadata": {},
   "source": [
    "Проверим рефлексивность. Чтобы выявить наличие единиц на главной диагонали, сгенерируем единичную матрицу нужной размерности, и проверим включается ли она в исходное отношение. Но можно и напрямую проверить, что элементы с i=j в отношении равны 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "23da8a2f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def reflexivity_check(array: list[list[int]]) -> bool:\n",
    "    return all(array[i][i] == 1 for i in range(max(len(array), len(array[0]))))\n",
    "\n",
    "\n",
    "reflexivity_check(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08976a67",
   "metadata": {},
   "source": [
    "Для проверки антирефлексивности необходимо проверить, что что элементы с i=j в отношении равны 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ab2ec981",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def antireflexivity_check(array: list[list[int]]) -> bool:\n",
    "    return all(array[i][i] == 0 for i in range(max(len(array), len(array[0]))))\n",
    "\n",
    "\n",
    "antireflexivity_check(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cbc0e84",
   "metadata": {},
   "source": [
    "Для проверки симметричности нужно проверить, что если в отношении i,j-ый элемент равен 1, то и j,i-ый элемент тоже равен единице\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "434cfe13",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def symmetry_check(array: list[list[int]]) -> bool:\n",
    "    return all(array[i][j] == array[j][i] for j in range(len(array[0])) for i in range(len(array)))\n",
    "\n",
    "\n",
    "symmetry_check(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a186d882",
   "metadata": {},
   "source": [
    "Для проверки антисимметричности нужно проверить, что если в отношении i,j-ый элемент равен единице, то и j,i-ый элемент равен нулю\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "7727ec98",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def antisymmetry_check(array: list[list[int]]) -> bool:\n",
    "    return all(array[i][j] != array[j][i] or i == j for j in range(len(array[0])) for i in range(len(array)))\n",
    "\n",
    "\n",
    "antisymmetry_check(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88678087",
   "metadata": {},
   "source": [
    "Для проверки транзитивности нужно проверить, что если i,j-ый и j,k-ый элементы принадлежат отношению, то и i,k-ый элемент тоже равен единице\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "518a0e6c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def transitivity_check(array: list[list[int]]) -> bool:\n",
    "    x = len(array[0])\n",
    "    y = len(array)\n",
    "    for x_1 in range(x):\n",
    "        for y_1 in range(y):\n",
    "            for x_2 in range(x):\n",
    "                if array[y_1][x_1] * array[x_1][x_2] and not array[y_1][x_2]:\n",
    "                    return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "\n",
    "transitivity_check(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16f83129",
   "metadata": {},
   "source": [
    "### Множество всех подмножеств\n",
    "\n",
    "Алгоритм Грея генерирует последовательность всех подмножеств п-элементного множества, причём каждое следующее подмножество получается из предыдущего удалением или добавлением в точности одного элемента.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f3f4a62f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Рефлективна - False\n",
      "Антирефлективна - False\n",
      "Симметрична - False\n",
      "Антисимметрична - False\n",
      "Транзитивна - True\n",
      "Замкнута - True\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# ваш код\n",
    "def some_funtion(first_array: list[list[int]], second_array: list[list[int]]) -> list[list[int]]:\n",
    "    if len(first_array) != len(second_array) or len(first_array[0]) != len(second_array[0]):\n",
    "        return None\n",
    "\n",
    "    x = len(first_array[0])\n",
    "    y = len(first_array)\n",
    "    new_matrix = [[0 for _ in range(x)] for _ in range(y)]\n",
    "    \n",
    "    for y_1 in range(y):\n",
    "        for x_1 in range(x):\n",
    "            for y_2 in range(y):\n",
    "                new_matrix[y_1][x_1] = int(new_matrix[y_1][x_1] or\n",
    "                                           first_array[y_1][y_2] * second_array[y_2][x_1])\n",
    "    \n",
    "    return new_matrix\n",
    "\n",
    "\n",
    "def some_function_check(array: list[list[int]]) -> bool:\n",
    "    return some_funtion(some_funtion(array, array), array) == \\\n",
    "        some_funtion(some_funtion(some_funtion(array, array), array), array)\n",
    "\n",
    "\n",
    "array = [[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0]]\n",
    "\n",
    "print(f\"\"\"\n",
    "Рефлективна - {reflexivity_check(array)}\n",
    "Антирефлективна - {antireflexivity_check(array)}\n",
    "Симметрична - {symmetry_check(array)}\n",
    "Антисимметрична - {antisymmetry_check(array)}\n",
    "Транзитивна - {transitivity_check(array)}\n",
    "Замкнута - {some_function_check(array)}\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc2c6a7d",
   "metadata": {},
   "source": [
    "### Транзитивное замыкание\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77642242",
   "metadata": {},
   "source": [
    "Транзитивное замыкание бинарного отношения, представленного в виде бинарной матрицы,\n",
    "представляет собой объединение положительных степеней (всех) исходного отношения\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "7a3af8c2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 1 0]\n",
      " [0 0 1 1]\n",
      " [1 0 0 0]\n",
      " [0 0 1 0]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "A = np.array([[0, 0, 1, 0],\n",
    "              [0, 0, 1, 1],\n",
    "              [1, 0, 0, 0],\n",
    "              [0, 0, 1, 0]])\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92d6fac0",
   "metadata": {},
   "source": [
    "Исходный алгоритм Уоршелла проще, поскольку он находит только транзитивное замыкание графа и не использует никакой информации о весах ребер. Алгоритм Флойда в основном является этим алгоритмом с дополнительными соображениями о таких весах. Алгоритм Флойда-Уоршалла решает проблему кратчайшего пути для всех пар. Соответственно, на вход алгоритма Флойда-Уоршалла нужно подавать взвешенноую матрицу бинарного отношения, в которой ненулевой элемент обозначает не только наличие отношения между i и j элементами, но и силу этой связи (выраженную положительным числом).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f071103e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def warshall(G):\n",
    "    W = G\n",
    "    n = len(G)\n",
    "    for k in range(n):\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                G[i, j] = G[i, j] or (G[i, k] and G[k, j])\n",
    "    return W"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "2c977eb9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 0, 1, 0],\n",
       "       [1, 0, 1, 1],\n",
       "       [1, 0, 1, 0],\n",
       "       [1, 0, 1, 0]])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "warshall(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87b5bb3e",
   "metadata": {},
   "source": [
    "Так как транзитивное замыкание показывает, что если есть путь из i-ой вершины в k-ую и из k-ой вершины в j-ую, то есть путь и из i-ой вершины в j-ую. Соответственно сама матрица отношения это пути дляны 1, если мы строим композицию RR, то в итоге получаем наличие пути, длины 2, а если выполняем обычное возведение в степень, то за счет сложения будем видеть количество путей, длина которых соответствует степени.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "3a6c20c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2, 0, 3, 0],\n",
       "       [4, 0, 5, 1],\n",
       "       [3, 0, 2, 0],\n",
       "       [2, 0, 3, 0]])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array_1 = ([[0, 0, 1, 0], [0, 0, 1, 1], [1, 0, 0, 0], [0, 0, 1, 0]])\n",
    "np.linalg.matrix_power(array_1, 1) + np.linalg.matrix_power(array_1, 2) + np.linalg.matrix_power(\n",
    "    array_1, 3)+np.linalg.matrix_power(array_1, 4)+np.linalg.matrix_power(array_1, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a52bca04",
   "metadata": {},
   "source": [
    "Поэтому встает закономерный вопрос, какой путь из предложенных будет иметь наименьшую длину?\n",
    "Ответ можно найти с помощью алгоритма Флойда-Уоршалла. Только зададим веса. Обратите внимание на нули, которые обозначают отсутствующие пути.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "dc53474a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 3, 0, 7],\n",
       "       [8, 0, 2, 0],\n",
       "       [5, 0, 0, 1],\n",
       "       [2, 0, 0, 0]])"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваша матрица\n",
    "graph = np.array([\n",
    "    [0, 3, 0, 7],\n",
    "    [8, 0, 2, 0],\n",
    "    [5, 0, 0, 1],\n",
    "    [2, 0, 0, 0]\n",
    "])\n",
    "\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "db277779",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 3., 5., 6.],\n",
       "       [5., 0., 2., 3.],\n",
       "       [3., 6., 0., 1.],\n",
       "       [2., 5., 7., 0.]])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ваш код\n",
    "def floyd_warshall(graph: np.ndarray) -> np.ndarray:\n",
    "    num_vertices = len(graph)\n",
    "    dist = np.array([[0 if i == j else graph[i][j] if graph[i][j] != 0 else np.inf for j in range(num_vertices)] for i in range(num_vertices)])\n",
    "\n",
    "    for k in range(num_vertices):\n",
    "        for i in range(num_vertices):\n",
    "            for j in range(num_vertices):\n",
    "                if dist[i][k] != np.inf and dist[k][j] != np.inf:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n",
    "\n",
    "    return dist\n",
    "\n",
    "\n",
    "floyd_warshall(graph)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}