Shortest path problem
id:
shortest-path-problem-205-3221422
title:
Shortest path problem
text:
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.
brand slug:
wiki
category slug:
encyclopedia
description:
Computational problem of graph theory
original url:
https://en.wikipedia.org/wiki/Shortest_path_problem
date created:
2002-02-26T15:45:58Z
date modified:
2024-09-10T17:47:18Z
main entity:
{"identifier":"Q1058754","url":"https://www.wikidata.org/entity/Q1058754"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/3/3b/Shortest_path_with_direct_weights.svg","width":512,"height":280}
fields total:
13
integrity:
16