I think the solution here is quite close to what Loki said. Every actor is a node and the films they share build and equivalence class, which comes down to an edge in the graph.

Now the trick is to avoid loops in the graph. Here you should google Johnson's algorithm for finding simple cycles. The idea rather simple, whenever you visit a node (actor) you mark it/him and do not traverse further when you find him again. It guarantees that the longest path might only be N-1 steps.

Together with building equivalence classes of the movies you end up with a rather small graph, which should be easy to traverse.

So you end up with a simpl construct:

struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner) {
        partners.push_back(partner);
    }

    const std::string   name;
    std::vector<actor*> partners;
}

class graph {
    AddActor(const std::string& name) {
        actors.emplace_back(std::make_unique<actor>(name));
    }
    void AddPartners(const std::string& name1, const std::string& name2) {
        actor* actor1 = nullptr;
        actor* actor2 = nullptr;
        for (auto&& act : actors) {
            if (act->name == name1) {
                actor1 = act.get();
                if(actor2)
                    break;
            } 
            if (act->name == name2) {
                actor2 = act.get();
                if(actor1)
                    break;
            }
        }
        actor1->AddPartner(actor2);
        actor2->AddPartner(actor1);
    }
private:
    std::vector<std::unique_ptr<actor>> actors;
}

Then what you need is a simple breadth first search to find the shortest path:

void findShortestLink(const std::string& name1, const std::string& name2) {
    actor* firstActor = (*std::find(actors.begin(), actors.get(), [&name1](auto&& act) { return act.get()->name == name1;}).get(); 
    std::queue<actor*> queue;
    queue.push(firstActor);
    std::unordered_set<actor*> visited;
    visited.insert(firstActor);
    while(!queue.empty()) {
        actor* current = queue.front();
        queue.pop();
        for (auto&& partner : partners) {
            if (visited.count(partner) == 0) {
                if (partner->name == name2) {
                    std::queue<actor*> emptyQueue;
                    std::swap(queue, emptyQueue);
                    break;
                } 
                visited.insert(partner);
                queue.push(partner);
            }
        }
    }
}

But how can you know how many movies you walked? Here you can add a member to the actors, that remembers the movie they come from.

 struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner) {
        partners.push_back(partner);
    }

    const std::string   name;
    std::vector<actor*> partners;
    actor* predecessor;
}

Now you can set them and walk them back if you found the right one

size_t findShortestLink(const std::string& name1, const std::string& name2) {
    actor* firstActor = (*std::find(actors.begin(), actors.get(), [&name1](auto&& act) { return act.get()->name == name1;}).get(); 
    std::queue<actor*> queue;
    queue.push(firstActor);
    std::unordered_set<actor*> visited;
    visited.insert(firstActor);
    while(!queue.empty()) {
        actor* current = queue.front();
        queue.pop();
        for (auto&& partner : partners) {
            if (visited.count(partner) == 0) {
                partner->predecessor = current;
                if (partner->name == name2) {
                    std::queue<actor*> emptyQueue;
                    std::swap(queue, emptyQueue);
                    size_t result = 0;
                    while (partner->predecessor != firstActor) {
                        result++;
                        partner = partner->predecessor;
                    }
                    return result;
                } 
                visited.insert(partner);
                queue.push(partner);
            }
        }
    }
    return 0;
}

Now how can we add the weights? This depends on personal preference. You can either make partners a std::vector<std::pair<actor*, size_t>> and add first and second appropriately or add a std::unordered_map<actor*, size_t> to the actor.

Any way you obviously just need to increment/multiply (depending on how your weight affects the score) result with the weight.

EDIT:

If you really need the movie info you should go with a multimap and create a simple struct that stores the movie data. Then the while clause would obviously be:

std::vector<std::vector<movieInfo>>;                   
while (partner->predecessor != firstActor) {
    result.emplace_back(partner->GetMovieInfo(partner->predecessor);
    partner = partner->predecessor;
}

Edit2: What to do about movies?

So you want to keep track of the movies. That should happen when you create a link between the two actors. The easiest way would be with an array of structures that hod the movie information.

We can easily adopt our actor class for that purpose

struct movieInfo {
    // Whatever you need here
}

struct actor {
    actor(const std::string& Name)
        : name(Name);

    void AddPartner(actor* partner, movieInfo&& info) {
        partners.push_back(partner);
        if (movies.count(partner) == 0) {
            movies.insert(std::make_pair<actor*, std::vector<movieInfo>(partner, std::vector<movieInfo>(1, std::move(info))));
        } else {
            movies.at(partner).emplace_back(std::move(info));
        }
    }

    const std::string   name;
    std::vector<actor*> partners;
    std::unordered_map<actor*, std::vector<movieInfo>> movies;
}

Now you can use the above alternation of the result and return a vector of the vector of movies

std::vector<std::vector<movieInfo>>;                   
while (partner->predecessor != firstActor) {
    result.emplace_back(partner->GetMovieInfo(partner->predecessor);
    partner = partner->predecessor;
}