diff --git a/api/docs/api.rst b/api/docs/api.rst
--- a/api/docs/api.rst
+++ b/api/docs/api.rst
@@ -1,22 +1,66 @@
 Graph traversal API
 ===================
 
-Visit
------
+Path
+----
 
-.. http:get:: /graph/visit/:swh_id
+.. http:get:: /graph/path/:src/:dst
 
-    Performs a graph traversal and returns explored paths (in the order of the
-    traversal).
+    Performs a graph traversal and returns the first found path from source to
+    destination.
 
-    :param string swh_id: starting point for the traversal, represented as a
+    :param string src: starting point for the traversal, represented as a
     `Software Heritage persitent identifier
     <https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html#persistent-identifiers>`_
+    :param string dst: ending point for the traversal, represented either as a
+    Software Heritage persitent identifier, or as an object type in which case
+    the traversal will stop on any node with same type.
+
+    :query string edges: edges types the traversal can follow, expressed as a
+    comma-separated list of ``src:dst`` strings (e.g.: ``"rev:rev,rev:dir"``).
+    If no string is provided, the traversal will use all types of edges.
+    :query string traversal: can be either ``dfs`` or ``bfs``, default to
+    ``dfs``
+    :query string direction: can be either ``forward`` or ``backward``, default
+    to ``forward``
+
+    :statuscode 200: no error
+    :statuscode 400: an invalid query string has been provided
+    :statuscode 404: requested starting node cannot be found in the graph
+
+    .. sourcecode:: http
+
+    HTTP/1.1 200 OK
+    Content-Type: application/json
+
+    {
+        "path": [
+            "swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35",
+            "swh:1:rev:52c90f2d32bfa7d6eccd66a56c44ace1f78fbadd",
+            "swh:1:rev:cea92e843e40452c08ba313abc39f59efbb4c29c",
+            "swh:1:rev:8d517bdfb57154b8a11d7f1682ecc0f79abf8e02",
+            ...
+        ]
+    }
+
+Explore
+-------
+
+.. http:get:: /graph/explore/:src/:dst
+
+    Returns all explored paths and nodes (in the order of the traversal), from
+    source to destination.
+
+    :param string src: starting point for the traversal, represented as a
+    `Software Heritage persitent identifier
+    <https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html#persistent-identifiers>`_
+    :param string dst: ending point for the traversal, represented either as a
+    Software Heritage persitent identifier, or as an object type in which case
+    the traversal will stop on any node with same type.
 
     :query string edges: edges types the traversal can follow, expressed as a
     comma-separated list of ``src:dst`` strings (e.g.: ``"rev:rev,rev:dir"``).
     If no string is provided, the traversal will use all types of edges.
-    :query string traversal: default to ``dfs``
     :query string direction: can be either ``forward`` or ``backward``, default
     to ``forward``
 
@@ -32,14 +76,23 @@
     {
         "paths": [
             [
-                "swh:1:cnt:94a9ed024d3859793618152ea559a168bbcbb5e2",
+                "swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35",
+                "swh:1:rev:52c90f2d32bfa7d6eccd66a56c44ace1f78fbadd",
                 ...
             ],
             [
-                "swh:1:dir:d198bc9d7a6bcf6db04f476d29314f157507d505",
+                "swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35",
+                "swh:1:rev:a31e58e129f73ab5b04016330b13ed51fde7a961",
                 ...
             ],
             ...
+        ],
+        "nodes": [
+            "swh:1:rev:f39d7d78b70e0f39facb1e4fab77ad3df5c52a35",
+            "swh:1:rev:52c90f2d32bfa7d6eccd66a56c44ace1f78fbadd",
+            ...
+            "swh:1:rev:a31e58e129f73ab5b04016330b13ed51fde7a961",
+            ...
         ]
     }