Constrained Shortest Path Dijkstra












0












$begingroup$


Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.



I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.



I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.



Thanks




EDIT:



My problem is similar to a-Autonomy Shortest Paths:
I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.



So for example given this graph:




S--R1--R2--F--D

······················/

··Z1----------Z2




Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.

This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.

As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.



I don't know whether I made it to clarify my self or not....but it would be nice if you give me any hint on how to do it.



Thanks






graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
    $endgroup$
    – Eff
    Aug 6 '14 at 20:56










  • $begingroup$
    It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
    $endgroup$
    – qaphla
    Aug 6 '14 at 21:05










  • $begingroup$
    Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
    $endgroup$
    – cama
    Aug 6 '14 at 21:55










  • $begingroup$
    Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06










  • $begingroup$
    This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06
















0












$begingroup$


Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.



I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.



I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.



Thanks




EDIT:



My problem is similar to a-Autonomy Shortest Paths:
I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.



So for example given this graph:




S--R1--R2--F--D

······················/

··Z1----------Z2




Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.

This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.

As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.



I don't know whether I made it to clarify my self or not....but it would be nice if you give me any hint on how to do it.



Thanks






graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
    $endgroup$
    – Eff
    Aug 6 '14 at 20:56










  • $begingroup$
    It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
    $endgroup$
    – qaphla
    Aug 6 '14 at 21:05










  • $begingroup$
    Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
    $endgroup$
    – cama
    Aug 6 '14 at 21:55










  • $begingroup$
    Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06










  • $begingroup$
    This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06














0












0








0





$begingroup$


Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.



I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.



I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.



Thanks




EDIT:



My problem is similar to a-Autonomy Shortest Paths:
I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.



So for example given this graph:




S--R1--R2--F--D

······················/

··Z1----------Z2




Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.

This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.

As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.



I don't know whether I made it to clarify my self or not....but it would be nice if you give me any hint on how to do it.



Thanks






graph-theory







share|cite|improve this question











$endgroup$




Here is my problem: I have my graph and I want to find the shortest path constrained in terms of number of vertex passed by.



I have tried to apply Dijkstra with some modifications but obviously for some graphs I obtained a sub-optimal solution. I want to achieve the optimal one.



I am pretty sure this has been done, but I don't know where to find it. I have found solution for having a fix number of vertex passed by (hops) but what I want instead of that is a constrain in the maximum number of hops, not a fixed one.



Thanks




EDIT:



My problem is similar to a-Autonomy Shortest Paths:
I want to go by car from S to D. I don't have enough fuel. I can stop at two(k) petrol stations in my way.



So for example given this graph:




S--R1--R2--F--D

······················/

··Z1----------Z2




Here for example from S to F the shortest and optimal path would be S-R1-R2-F, refuelling at R1 and R2.

This path is also valid for going from S to D, I can refuel at R1 and R2. However, that is a suboptimal path, since for going from S to D refueling at max 2 times I might have a better path refuelling at Z1 and Z2.

As you see my problem is not in terms of hops, is in terms of 'where do I refuel', that as in Dijkstra I base the status of D based on the predecessor F, suboptimal path might not be reached.



I don't know whether I made it to clarify my self or not....but it would be nice if you give me any hint on how to do it.



Thanks






graph-theory




graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 6 '14 at 22:51







user940

















asked Aug 6 '14 at 20:47









camacama

86




86












  • $begingroup$
    If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
    $endgroup$
    – Eff
    Aug 6 '14 at 20:56










  • $begingroup$
    It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
    $endgroup$
    – qaphla
    Aug 6 '14 at 21:05










  • $begingroup$
    Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
    $endgroup$
    – cama
    Aug 6 '14 at 21:55










  • $begingroup$
    Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06










  • $begingroup$
    This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06


















  • $begingroup$
    If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
    $endgroup$
    – Eff
    Aug 6 '14 at 20:56










  • $begingroup$
    It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
    $endgroup$
    – qaphla
    Aug 6 '14 at 21:05










  • $begingroup$
    Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
    $endgroup$
    – cama
    Aug 6 '14 at 21:55










  • $begingroup$
    Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06










  • $begingroup$
    This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
    $endgroup$
    – xavierm02
    Aug 6 '14 at 22:06
















$begingroup$
If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
$endgroup$
– Eff
Aug 6 '14 at 20:56




$begingroup$
If I understand you correctly, just take your graph and put a weight of $1$ on each edge. Then Dijkstra's algorithm will give the solution which passes the fewest edges (and therefore vertices).
$endgroup$
– Eff
Aug 6 '14 at 20:56












$begingroup$
It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
$endgroup$
– qaphla
Aug 6 '14 at 21:05




$begingroup$
It sounds like the OP wants an implementation of Dijkstra's algorithm that works on a graph that is already weighted, but such that the path found is never longer than some prespecified length. This solution therefore does not work.
$endgroup$
– qaphla
Aug 6 '14 at 21:05












$begingroup$
Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
$endgroup$
– cama
Aug 6 '14 at 21:55




$begingroup$
Yes, graph is already weighted. Could you please check on the new edit of the question, please? Thanks
$endgroup$
– cama
Aug 6 '14 at 21:55












$begingroup$
Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
$endgroup$
– xavierm02
Aug 6 '14 at 22:06




$begingroup$
Define the size of the path as the number of edges it contains and the length of a path as the lengths of each edge. If I understood you properly, you want to get the path of minimal length which has size $le n$ for some fixed $n$. And a way to achieve that is to compute $n$ values instead of $1$ for each node: instead of computing the length of the shortest path from the origin, you compute the length of the shortest path from the origin whose size is $le k$ for $k$ from $1$ to $n$.
$endgroup$
– xavierm02
Aug 6 '14 at 22:06












$begingroup$
This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
$endgroup$
– xavierm02
Aug 6 '14 at 22:06




$begingroup$
This can probably be improved by using a list instead of an array (because otherwise, when you set a new value for the $k^{th}$ item of the array, you also have to set it in all the following items that have a greater value).
$endgroup$
– xavierm02
Aug 6 '14 at 22:06










1 Answer
1






active

oldest

votes


















0












$begingroup$

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.



Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:




  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there

  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)


In this way, you should be able to remove the paths that are going to violate the constraint.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
    $endgroup$
    – Fabio Somenzi
    Mar 2 '17 at 1:39













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f889418%2fconstrained-shortest-path-dijkstra%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









0












$begingroup$

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.



Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:




  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there

  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)


In this way, you should be able to remove the paths that are going to violate the constraint.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
    $endgroup$
    – Fabio Somenzi
    Mar 2 '17 at 1:39


















0












$begingroup$

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.



Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:




  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there

  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)


In this way, you should be able to remove the paths that are going to violate the constraint.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
    $endgroup$
    – Fabio Somenzi
    Mar 2 '17 at 1:39
















0












0








0





$begingroup$

Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.



Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:




  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there

  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)


In this way, you should be able to remove the paths that are going to violate the constraint.






share|cite|improve this answer











$endgroup$



Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting.



Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak:




  1. when you complete a vertex, you also put a flag F to mark the number of steps it takes to get there

  2. for a newly completed vertex, look at the outgoing edges and check the "distance from destination" of the pointed vertices. If the sum of that distance with the flag F is larger than your constraint, then delete the edge (or set its cost to a really large number)


In this way, you should be able to remove the paths that are going to violate the constraint.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Aug 6 '14 at 22:26

























answered Aug 6 '14 at 22:13









bartgolbartgol

5,0381419




5,0381419












  • $begingroup$
    Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
    $endgroup$
    – Fabio Somenzi
    Mar 2 '17 at 1:39




















  • $begingroup$
    Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
    $endgroup$
    – Fabio Somenzi
    Mar 2 '17 at 1:39


















$begingroup$
Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
$endgroup$
– Fabio Somenzi
Mar 2 '17 at 1:39






$begingroup$
Suppose the threshold is $3$ edges. If I understand this approach, the problem is that there may be two paths $pi_1$ and $pi_2$ from source to some vertex $v$ such that $pi_1$ uses one edge, while $pi_2$ uses two. If $pi_2$ is shorter than $pi_1$, the latter is effectively forgotten because $F_v = 2$. If going from $v$ to the target requires at least two more edges, one comes to the incorrect conclusion that there is no path from source to target that goes through $v$. The dynamic programming approach in the comments by @xavierm02 does not have this problem.
$endgroup$
– Fabio Somenzi
Mar 2 '17 at 1:39




















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f889418%2fconstrained-shortest-path-dijkstra%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Index of /

This page is only for reference, If you need detailed information, please check here
Read more

Tribalistas

Image
  Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
Read more

Filisteus

Image
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo, o que compromete a verificabilidade (desde Outubro de 2011) . Por favor, insira mais referências no texto. Material sem fontes poderá ser removido. — Encontre fontes: Google (notícias, livros e acadêmico) Estados Filisteus ca. 830 a.C. Pentápolis filisteia (em vermelho) Os filisteus (do פְּלְשְׁתִּים; transl.: plishtim ) foram um povo que ocupou a costa sudoeste de Canaã, com seu território nomeado como Filístia em contextos posteriores. Teoriza-se que eles se originaram entre os "povos do mar" [ 1 ] . A arqueologia moderna também sugeriu os primeiros laços culturais com o mundo micênico na Grécia. Apesar de eles terem adotado a língua e a cultura local cananeia antes de deixar quaisquer textos escritos (e posteriormente adotarem a língua Aramaica), uma origem indo-europeia tem sido sugerida para um grande número de palavras filisteias conhecidas que so...
Read more