Consider the problem of finding the shortest path to a destination city from a start city using roads $($e$.$g$.,$ traveling from Arad to Bucharest$)$ using A$*$ search. Which of these heuristics are admissible? There could be multiple such heuristics; select all for full credit.

Consider the problem of finding the shortest path to a destination city from a start city using roads $($e$.$g$.,$ traveling from Arad to Bucharest$)$ using A$*$ search. Which of these heuristics are admissible? There could be multiple such heuristics; select all for full credit.

Twice the Euclidean distance $("$as the crow flies"$)$ between a city and destination city

Euclidean distance $("$as the crow flies"$)$ between a city and start city

Manhattan distance $("$go first east$/$west and then north$/$south$")$ between a city and start city

Euclidean distance $("$as the crow flies"$)$ between a city and destination city

Manhattan distance $("$go first east$/$west and then north$/$south$")$ between a city and destination city

heuristic is $0$ for every city

heuristic is $1$ for every city