Shortest Path & Dijkstra's Algorithm

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/11

flashcard set

Earn XP

Description and Tags

Vocabulary practice flashcards based on lecture notes on shortest paths and Dijkstra's algorithm.

12 Terms

1
New cards

Distance Between Vertices d(u,v)d(u,v)

The length of the shortest path between vertex uu and vertex vv in a graph GG.

2
New cards
<p>Graph $$G$$ Example (Section 3.1)</p>

Graph GG Example (Section 3.1)

A weighted graph with 4 vertices (v1,v2,v3,v4v_1, v_2, v_3, v_4) used to demonstrate finding the distance d(v1,v4)d(v_1, v_4) and path between vertices.

3
New cards

Dijkstra's Algorithm

An algorithm used to find the shortest path from a starting vertex ss to a target vertex tt in a weighted graph GG.

4
New cards

Input for Dijkstra's Algorithm

A weighted graph GG and specified vertices s,t×V(G)s, t \times V(G).

5
New cards

Step 1 of Dijkstra's Algorithm

Label vertex ss with π(s)=0π(s) = 0, label all other vertices v∈V(G)−{s}v \in V(G) - \{s\} with π(v)=∞π(v) = \infty, and set T=V(G)T = V(G).

6
New cards

Step 2 of Dijkstra's Algorithm

Select a vertex u∈Tu \in T with the minimum label value π(u)π(u).

7
New cards

Step 3 of Dijkstra's Algorithm

If u=tu = t, stop the process and output the result message.

8
New cards

Step 4 of Dijkstra's Algorithm

For each edge e=uve = uv where v∈Tv \in T, update the label of vertex vv to π(v)=min⁡{π(v),π(u)+w(e)}π(v) = \min\{π(v), \pi(u) + w(e)\}.

9
New cards

Step 5 of Dijkstra's Algorithm

Update the unvisited set T=T−{u}T = T - \{u\} and return to Step 2.

10
New cards
<p>Dijkstra's Algorithm Workflow</p>

Dijkstra's Algorithm Workflow

The complete 5-step algorithmic procedure for iteratively calculating vertex labels π(v)π(v) to find the shortest path.

11
New cards
<p>8-Vertex Shortest Path Problem (Section 3.3)</p>

8-Vertex Shortest Path Problem (Section 3.3)

An 8-vertex graph problem (v1v_1 through v8v_8) tracking vertex labels π(vi)π(v_i) across iterations to find the shortest path from v1v_1 to v8v_8.

12
New cards
<p>Shortest Path Summary Table (Section 3.4)</p>

Shortest Path Summary Table (Section 3.4)

A table layout used to record the origin vertex, destination vertices (v2v_2 to v8v_8), specific shortest path sequences, and total path lengths.