Scribd
Upload
4 views1 page

Study 2

Uploaded by

ilana.radparvar26
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Study 2

Uploaded by

ilana.radparvar26
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Shortest Path Problem

Given two vertices, find the shortest route between them.


Common algorithm:
Dijkstra's Algorithm
Steps:
1. Start at the source vertex.
2. Assign distance 0 to the source and infinity to all others.
3. Visit the nearest unvisited vertex.
4. Update neighboring distances.
5. Repeat until all vertices are visited.
Applications:
● GPS navigation
● Internet routing
● Logistics planning

Graph Coloring
Graph coloring assigns colors to vertices so that adjacent vertices have different
colors.
Goal:
Use the fewest colors possible.
Applications:
● Scheduling problems
● Register allocation in computers
● Map coloring
Interesting Fact:
Any flat map can be colored using at most four colors. This is known as the Four
Color Theorem.
●

You might also like