b'\n_START_ARTICLE_\nCaminho (teoria dos grafos)\n_START_PARAGRAPH_\nEm teoria dos grafos, um caminho em um grafo \xc3\xa9 uma\xc2\xa0sequ\xc3\xaancia\xc2\xa0finita ou infinita de v\xc3\xa9rtices conectados por uma sequ\xc3\xaancia de arestas que, na maioria das defini\xc3\xa7\xc3\xb5es, s\xc3\xa3o todos diferentes uns dos outros. O primeiro v\xc3\xa9rtice \xc3\xa9 chamado de v\xc3\xa9rtice inicial e o \xc3\xbaltimo \xc3\xa9 chamado de v\xc3\xa9rtice final. Em um grafo direcionado, um caminho dirigido (\xc3\xa0s vezes chamado de dipath) \xc3\xa9 uma sequ\xc3\xaancia de arestas que se conectam a uma sequ\xc3\xaancia de v\xc3\xa9rtices, mas com a restri\xc3\xa7\xc3\xa3o de que as arestas sejam todas dirigidas no mesmo sentido._NEWLINE_Os caminhos s\xc3\xa3o conceitos fundamentais de teoria de grafos, descrito nas se\xc3\xa7\xc3\xb5es introdut\xc3\xb3rias da maioria dos textos sobre teoria dos grafos.\n_START_SECTION_\nDefini\xc3\xa7\xc3\xa3o formal\n_START_PARAGRAPH_\nUm passeio de dist\xc3\xa2ncia\xc2\xa0\xc2\xa0em um grafo \xc3\xa9 uma sequ\xc3\xaancia alternante de v\xc3\xa9rtices e arestas\xc2\xa0, que come\xc3\xa7a e termina em v\xc3\xa9rtices. Um caminho \xc3\xa9 um passeio na qual todos os v\xc3\xa9rtices (exceto possivelmente o primeiro e o \xc3\xbaltimo) s\xc3\xa3o distintos, enquanto uma trilha \xc3\xa9 um passeio no qual todas as arestas\xc2\xa0(ou edges, em ingl\xc3\xaas) s\xc3\xa3o distintas._NEWLINE_Certos autores requerem que as arestas e v\xc3\xa9rtices sejam distintos. Alguns, por\xc3\xa9m, n\xc3\xa3o procedem dessa forma, preferindo usar o termo caminho simples ao inv\xc3\xa9s para se referir a um caminho que n\xc3\xa3o repete v\xc3\xa9rtices. Um caminho simples em um grafo  \xc3\xa9 uma sequ\xc3\xaancia de v\xc3\xa9rtices de , por exemplo, , tal que  para todo ._NEWLINE_Se o grafo \xc3\xa9 n\xc3\xa3o dirigido, ent\xc3\xa3o os n\xc3\xb3s de\xc2\xa0 s\xc3\xa3o\xc2\xa0 e . Se o grafo \xc3\xa9 dirigido, ent\xc3\xa3o\xc2\xa0 \xc3\xa9 um arco de  a .\n_START_SECTION_\nEncontrando caminhos\n_START_PARAGRAPH_\nV\xc3\xa1rios algoritmos existem para encontrar os caminhos\xc2\xa0mais curto e mais longo\xc2\xa0em grafos, com a diferen\xc3\xa7a de que o primeiro problema \xc3\xa9 computacionalmente mais f\xc3\xa1cil do que o \xc3\xbaltimo._NEWLINE_O\xc2\xa0algoritmo de Dijkstra\xc2\xa0produz uma lista de caminhos mais curtos de um v\xc3\xa9rtice "fonte" a todos os outros v\xc3\xa9rtices em grafos direcionados e n\xc3\xa3o-direcionados com pesos n\xc3\xa3o-negativos nas arestas (ou nenhum peso), enquanto o\xc2\xa0algoritmo de Bellman\xe2\x80\x93Ford\xc2\xa0pode ser aplicado para grafos dirigidos com pesos negativos nas arestas. O algoritmo de Floyd\xe2\x80\x93Warshall\xc2\xa0pode ser usado para encontrar o menor caminho entre todos os pares de v\xc3\xa9rtices em grafos ponderados dirigidos.'