(a) Let's assign to each lattice point $P$ the number $f(P)$ which is the sum of the distances from $P$ to the $n$ constant vertices.
We will use a few lemmas to solve this problem.
Lemma 1. If $ABCD$ is a rhombus of side length $1$, where $A, B, C, D$ are lattice points so that $\angle BAC = \angle BDC = 60$, then we have $f(A) + f(C) \ge f(B) + f(D).$
Proof . It suffices to show this when there is only one $A_i$, then sum over all $A_i$'s. This is not hard to show by casework on where the $A_i$ is.
$\blacksquare$
Lemma 2. If $A, B, C$ are three collinear lattice points so that $AB = BC = 1$, then $f(A) + f(C) \ge 2 f(B).$
Proof. This is proven in the same way as Lemma $1.$
$\blacksquare$
Lemma 3. If $ABCD$ is a parallelogram so that $A, B, C, D$ are lattice points, its sides are parallel to the gridlines of the triangular lattice, and $\angle BAC = 60$, then we have $f(A) + f(C) \ge f(B) + f(D).$
Proof. Sum Lemma $1$ over all "sub-rhombi" of $ABCD$ which have parallel sides to $ABCD$ and are of length $1.$All interior points and lattice points on the perimeter of $ABCD$ appear an equal number of times on either side of the $\ge$ sign, except for $A, C$ which appear once each to the left of the $\ge$ sign, and $B, D$ which appear once each to the right of the $\ge $sign. This implies the lemma.
$\blacksquare$
Lemma 4. If $A, B, C, D$ are four lattice points so that $AD = t, AB = 1, BC = t-1, CD = t-1$ for some $t \ge 3$ and $AD$ lies entirely on some gridline, then $f(A) + f(D) \ge f(B) + f(C).$
Proof. Our strategy will be to use Lemma $2$ repeatedly. Let's label the lattice points on $AD$ $P_0, P_1, \cdots, P_t$ in the obvious manner, with $A = P_0$ and $D = P_t.$ Notice that by Lemma $2$ we have:
$$f(P_0) - f(P_1) \ge f(P_1) - f(P_2) \ge f(P_2) - f(P_3) \ge \cdots \ge f(P_{t-1}) - f(P_t).$$
This implies the lemma.
$\blacksquare$
From here, we're ready to solve the problem.
Suppose that our process ended at $A$, where $f(A)$ is less than or equal to $f$ of all its neighbors. Assume that $A$ is not the point where $f(A)$ is minimized, for contradiction. Let $B$ be the point closest to $A$ such that $f(B)$ (where "closeness" is measured in any sensible manner).
We consider two cases.
Case 1. $AB$ lies on a gridline.
Then, since $AB$ is clearly not $1$, we can consider points $C, D$ on segment $AB$ so that $AC = DB = 1.$ Then Lemma $4$ implies that $2 f(A) > f(A) + f(B) \ge f(C) + f(D)$, and so one of $f(C), f(D) < f(A).$ But $C, D$ are both closer to $A$ than $B$, contradiction.
Case 2. $AB$ doesn't lie on a gridline.
Then, there are points $C, D$ so that $ACBD$ is a parallelogram with $\angle CAD = \angle CBD = 60.$ Lemma $3$ then implies that $f(C) + f(D) \le f(A) + f(B) < 2f(A)$, so one of $f(C), f(D) < f(A).$ But $C, D$ are both closer to $A$ than $B$, contradiction.
As we've derived a contradiction in all cases, the problem is finished.
$\square$
(b) No, we can construct a counterexample as follows.
Our vertices will be $P_1, P_2, A_1, A_2, A_3, A_4, A_5, B_1, B_2, B_3, B_4, B_5.$
Start by connecting $P_2$ to all the $B_i$'s and $P_1$ to all the $A_i$'s. Now, for each $1 \le i \le 5$, connect $A_i$ to $B_i.$
Let $B_1, B_2, \cdots, B_5$ be the five constant points. Define $f$ similarly as in part (a). Then we have that $f(P_1) = 10$, $f(P_2) = 5$, $f(A_i) = 13$, and $f(B_i) = 8$ for all $1 \le i \le 5.$ If we begin our algorithm at $P_1$, then since all neighbors of $P_1$ have larger $f$ value (they all have $13$), our algorithm will tell us that $A$ is the global minimum of $f.$ However, that's actually $B$, which attains $5.$
$\square$