How can I modify Dijkstra's algorithm to get the longest path most of the time?

Question

I know that finding the longest path is an NP Hard problem.

What was asked from us was to change Dijkstra's algorithm to find the longest path by adding another parameter to the algorithm. A parameter like the distance from the source to the given vertex, the vertex predecessors, successors, number of edges...For example, we could extract the vertex from the queue depending on a parameter other than the max distance or we could another queue...

What we did first was to change the initialization so that all vertices distances = 0 except the source node, that = infinity. Then we extracted from the queue of vertices the one with the biggest distance. Then, we inverted the relaxation sign, so that the vertex saves the distance if it is bigger that its current distance.

What parameter could I add that would improve Dijkstra's performance in finding a longest path? It doesn't have to work 100% of the time.

This is Dijkstra's algorithm:

ShortestPath(G, v)
  init D array entries to infinity
  D[v]=0
  add all vertices to priority queue Q
  while Q not empty do
     u = Q.removeMin()
     for each neighbor, z, of u in Q do
       if D[u] + w(u,z) < D[z] then
          D[z] = D[u] + w(u,z)
          Change key of z in Q to D[z]
 return D as shortest path lengths

This is our modified version:

 ShortestPath(G, v)
   init D array entries to 0
   D[v]=infinity //source vertex
   add all vertices to priority queue Q
   while Q not empty do
     u = Q.removeMax()
     for each neighbor, z, of u in Q do
        if D[u] + w(u,z) > D[z] then
          D[z] = D[u] + w(u,z)
          Change key of z in Q to D[z]
   return D as shortest path lengths