Shortest Path Problem #10

 Definition:

‘Find the shortest path between nodes on a graph. Each variation has its own optimal algorithm. In the next slides you will learn. The basic vocabulary for the different variations

Algorithm type: –

Heuristic Solves the problem faster, but may not get the best result – optimal Ts guaranteed to return the best result but may be slower than Heuristic Algorithms

Graph Types for Shortest Path 1: –

Directed / Indirect graphs in an in directed graph you can always traverse one edge both ways TN a directed graph in only one direction. – cyclic / A cyclic graph: An a cyclic graph contains no cycles

Graph Types for shortest path 2: –

DAG: Directed A cyclic Graph A directed graph that has no cycles (if you follow a path you never meet the same node twice) – Tree: A cyclic connected in directed graph (In computer science we have recently used’ directed rooted trees

Problem categories 1: –

SSSP: single – source – shortest – path Find the shortest paths from one start – node to every other node – APSP: A11 – pair – shortest – path ‘Find the shortest paths between all’ pair combinations of nodes

Problem categories 2: –

SPSP: single – pair – shortest – path Find the shortest paths from one (start – node to one other node – SDSP: single – destination – s – p Find the shortest paths from all start nodes to one destination node

Graph weight properties 1: –

weighted Graph. Numbers are assigned to the edges (recently represented costs on the 1length of a way) – Unweighted graph A11 edges has the same weight 1

Graph weight properties 2: –

 Negative weights allowed. Edges can have negative weights (this can result in infinitely short paths) – Non-negative graph. The weights of the edges are greater than or equal to