3 Test Algorithm 1 for solving the  APSP matrix when the graph has negative weights.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e919a87e",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "#Algorithm 1 works when the graph has negative weights. \n",
    "#However, it does not work when the graph has negative circles. \n",
    "#The Floyd-Warshall algorithm does not either.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "35ff248d",
   "metadata": {},
   "outputs": [],
   "source": [
    "exec(open(\"./funcs/tool_funcs.py\").read())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5faa263b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortest_path_n_to_r(distance_matrix, shortest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for t in range(n):\n",
    "        m_jump =  distance_matrix[n,t] + shortest_path_matrix[t,r]\n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.min(max_jump_list)\n",
    "\n",
    "def shortest_path_r_to_n(distance_matrix, shortest_path_matrix, n, r):\n",
    "    max_jump_list = []\n",
    "    for t in range(n):\n",
    "        m_jump =  shortest_path_matrix[r,t] + distance_matrix[t, n] \n",
    "        max_jump_list.append(m_jump)\n",
    "    return np.min(max_jump_list)\n",
    "\n",
    "     \n",
    "def cal_n_shortest_path(distance_matrix, shortest_path_matrix, n):\n",
    "    for r in range(n):\n",
    "        shortest_path_matrix[n,r] = shortest_path_n_to_r(distance_matrix, shortest_path_matrix, n, r)\n",
    "        shortest_path_matrix[r,n] = shortest_path_r_to_n(distance_matrix, shortest_path_matrix, n, r)\n",
    "        \n",
    "    for i in range(n):        \n",
    "        for j in range(n):\n",
    "            if i < j:\n",
    "                shortest_path_matrix[i,j] =  update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, i, j)\n",
    "                shortest_path_matrix[j,i] =  update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, j, i)\n",
    "                \n",
    "def update_shortest_path_ij(distance_matrix, shortest_path_matrix, n, i, j):\n",
    "    m1 = shortest_path_matrix[i,j]\n",
    "    m2 =  shortest_path_matrix[i,n] + shortest_path_matrix[n,j] \n",
    "    return np.min((m1,m2))\n",
    "\n",
    "def cal_shortest_path_matrix_algo_1_python(distance_matrix):\n",
    "    \n",
    "  \n",
    "    N = len(distance_matrix)\n",
    "   \n",
    "    shortest_path_matrix = np.zeros((N,N))\n",
    "\n",
    "    shortest_path_matrix[0,1] = distance_matrix[0,1]\n",
    "    shortest_path_matrix[1,0] = distance_matrix[1,0]\n",
    " \n",
    "    for kk in range(2,N):\n",
    "        cal_n_shortest_path(distance_matrix, shortest_path_matrix, kk)\n",
    "    return shortest_path_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "562c9604",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 10)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 10\n",
    " \n",
    "dist_matrix = create_distance_matrix(N)\n",
    "\n",
    "dist_matrix.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d95193b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0., 617., 159.,   1., 117., 214., 349., 632., 573., 401.],\n",
       "       [919.,   0., 147., 902., 802., 963.,  88., 340.,  63., 174.],\n",
       "       [771., 329.,   0., 575.,  62., 518., 842., 229., 566., 504.],\n",
       "       [ 49., 896., 101.,   0., 651., 849., 504.,  25., 639., 876.],\n",
       "       [714., 197., 428., 639.,   0., 132., 174., 543., 965., 472.],\n",
       "       [481., 717., 552., 787., 291.,   0.,  85., 513., 169., 984.],\n",
       "       [789., 235., 348., 859., 395.,  44.,   0., 221., 233., 218.],\n",
       "       [164., 103., 622., 621., 284.,  38., 625.,   0., 951.,   4.],\n",
       "       [620., 153., 153., 383., 106., 878., 792., 913.,   0.,  58.],\n",
       "       [730., 384., 244., 293., 441., 457., 447., 697., 360.,   0.]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0f5f19f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0., 617., 159.,   1., 117., 214., 349., 632., 573., 401.],\n",
       "       [919.,   0., 147., 902., 802., 963.,  -8., 340.,  63., 174.],\n",
       "       [771., 329.,   0.,  -2.,  62., 518., 842., 229., 566., 504.],\n",
       "       [ 49., 896., 101.,   0., 651., 849., 504.,  25., 639.,  -3.],\n",
       "       [714., 197., 428., 639.,   0., 132., 174., 543., 965., 472.],\n",
       "       [481., 717., 552., 787., 291.,   0.,  85., 513., 169., 984.],\n",
       "       [789., 235., 348., 859., 395.,  44.,   0., 221., 233., 218.],\n",
       "       [164., 103., 622., 621., 284.,  38., 625.,   0., 951.,   4.],\n",
       "       [620., 153., 153., 383., 106., 878., 792., 913.,   0.,  58.],\n",
       "       [730., 384., 244., 293., 441., 457., 447., 697., 360.,   0.]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist_matrix[2,3] = -2\n",
    "\n",
    "dist_matrix[3,9] = -3\n",
    "\n",
    "dist_matrix[1,6] = -8\n",
    "dist_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "10d9804a",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "shortest_path_matrix_floyd_warshall = floyd_warshall(dist_matrix)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a3bfee8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "63d07af9",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "shortest_path_matrix_algo_1 = cal_shortest_path_matrix_algo_1_python(dist_matrix)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b1032168",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print(np.allclose(shortest_path_matrix_algo_1, shortest_path_matrix_floyd_warshall)) \n",
    "print(np.sum(np.abs(shortest_path_matrix_algo_1 - shortest_path_matrix_floyd_warshall))) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f3c28d5d",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0., 129., 102.,   1., 117.,  64., 121.,  26., 192.,  -2.],\n",
       "       [194.,   0., 147., 145., 169.,  36.,  -8., 170.,  63., 121.],\n",
       "       [ 47., 126.,   0.,  -2.,  62.,  61., 118.,  23., 189.,  -5.],\n",
       "       [ 49., 128., 101.,   0., 163.,  63., 120.,  25., 191.,  -3.],\n",
       "       [391., 197., 344., 342.,   0., 132., 174., 367., 260., 318.],\n",
       "       [369., 320., 322., 320., 275.,   0.,  85., 306., 169., 227.],\n",
       "       [385., 235., 348., 346., 319.,  44.,   0., 221., 213., 218.],\n",
       "       [164., 103., 248., 165., 272.,  38.,  95.,   0., 166.,   4.],\n",
       "       [200., 153., 153., 151., 106., 189., 145., 176.,   0.,  58.],\n",
       "       [291., 370., 244., 242., 306., 305., 362., 267., 360.,   0.]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_matrix_algo_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "bcbf1ebe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0., 129., 102.,   1., 117.,  64., 121.,  26., 192.,  -2.],\n",
       "       [194.,   0., 147., 145., 169.,  36.,  -8., 170.,  63., 121.],\n",
       "       [ 47., 126.,   0.,  -2.,  62.,  61., 118.,  23., 189.,  -5.],\n",
       "       [ 49., 128., 101.,   0., 163.,  63., 120.,  25., 191.,  -3.],\n",
       "       [391., 197., 344., 342.,   0., 132., 174., 367., 260., 318.],\n",
       "       [369., 320., 322., 320., 275.,   0.,  85., 306., 169., 227.],\n",
       "       [385., 235., 348., 346., 319.,  44.,   0., 221., 213., 218.],\n",
       "       [164., 103., 248., 165., 272.,  38.,  95.,   0., 166.,   4.],\n",
       "       [200., 153., 153., 151., 106., 189., 145., 176.,   0.,  58.],\n",
       "       [291., 370., 244., 242., 306., 305., 362., 267., 360.,   0.]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_path_matrix_floyd_warshall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7019befc",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "714ff4ca",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}